COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input acphdr % Section 4.5
C00019 00003	%folio 476 galley 4  Mostly unreadable tape. (C) Addison-Wesley 1978	*
C00036 00004	%folio 479 galley 5 Tape mostly unreadable. (C) Addison-Wesley 1978	*
C00048 00005	%folio 482 galley 6  Mostly hopeless. (C) Addison-Wesley 1978	*
C00056 00006	%folio 488 galley 7  Total loss. (C) Addison-Wesley 1978	*
C00069 00007	%folio 492 galley 8  Bad spots. (C) Addison-Wesley 1978		*
C00087 00008	%folio 496 galley 9  Bad spots. (C) Addison-Wesley 1978	*
C00106 00009	%folio 500 galley 10  Bad spots. (C) Addison-Wesley 1978	*
C00126 00010	% new material  (C) Addison-Wesley 1980	*
C00150 00011	%folio 505 galley 11  (C) Addison-Wesley 1978	*
C00154 00012	%folio 508 galley 12  Bad beginning. (C) Addison-Wesley 1978	*
C00168 00013	%folio 512 galley 13  Total loss. (C) Addison-Wesley 1978	*
C00194 00014	\vfill\eject\end
C00210 ENDMK
C⊗;
\input acphdr % Section 4.5
\open0=tmp.inx
\runninglefthead{ARITHMETIC} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{SECTION 4.5.4 of THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{RATIONAL ARITHMETIC}
\section{4.5.3}
\eject
\setcount0 364
\ninepoint
\exno 44. [M25] Suppose we are doing fixed slash arithmetic in which
$(u/u↑\prime)$ is representable if and only if $|u|<M$ and $0≤u↑\prime<N$ and
$\gcd(u,u↑\prime)=1$. Prove or disprove the identity $\biglp (u/u↑\prime)\oplus
(v/v↑\prime)\bigrp\ominus(v/v↑\prime)=(u/u↑\prime)$ for all representable
$(u/u↑\prime)$ and $(v/v↑\prime)$, provided that $u↑\prime<\sqrt N$ and no
overflow occurs.

\exno 45. [\HM48] Develop the analysis of algorithms for computing the gcd of
three or more integers.
%folio 476 galley 4  Mostly unreadable tape. (C) Addison-Wesley 1978	*
\runningrighthead{FACTORING INTO PRIMES}
\section{4.5.4}
\sectionskip
\sectionbegin{4.5.4. Factoring into Primes}
Several of the computational methods we have
\inxf{Factorization: Discovering factors. Of integers,}
encountered in this book rest on the fact that every positive
integer $n$ can be expressed in a unique way in the form
$$n = p↓1p↓2 \ldotsm p↓t,\qquad p↓1 ≤ p↓2 ≤ \cdots ≤ p↓t,\eqno(1)$$
where each $p↓k$ is \α{prime}.\xskip (When $n=1$, this equation holds for
$t=0$.)\xskip It is unfortunately not a simple matter to find this
prime factorization of $n$, or to determine whether or not $n$ is prime. So
far as anyone knows, it is a great deal harder to factor a large number $n$
than to compute the greatest common divisor of two large numbers $m$ and $n$;
therefore we should avoid factoring large numbers whenever possible. But several
ingenious ways to speed up the factoring process have been discovered, and we will
now investigate some of them.

\subsectionbegin{Divide and factor} First let us consider the most obvious
algorithm for factor\-ization: If $n>1$, we can divide $n$ by successive primes
$p=2$, 3, 5, $\ldots$ until discovering the smallest $p$ for which $n\mod p=0$.
Then $p$ is the smallest prime factor of $n$, and the same process may be applied
to $n←n/p$ in an attempt to divide this new value of $n$ by $p$ and by higher
primes. If at any stage we find that $n\mod p≠0$ but $\lfloor n/p\rfloor≤p$,
we can conclude that $n$ is prime; for if $n$ is not prime then by
(1) we must have $n ≥ p↓1↑2$, but $p↓1 > p$ implies that
$p↓1↑2 ≥ (p + 1)↑2 > p(p + 1) > p↑2 + (n \mod p)≥\lfloor
n/p\rfloor p + (n \mod p) = n$. This leads us to the following
procedure:

\algbegin Algorithm A (Factoring by division).
Given a positive integer $N$, this algorithm finds the prime
factors $p↓1 ≤ p↓2 ≤ \cdots ≤ p↓t$ of $N$ as in Eq.\ (1). The
method makes use of an auxiliary sequence of ``trial divisors''
$$2 = d↓0 < d↓1 < d↓2 < d↓3 < \cdotss,\eqno (2)$$
which includes all prime numbers $≤ \sqrt N$ (and
which may also include values that are {\sl not} prime, if
it is convenient to do so). The sequence of $d$'s must also
include at least one value such that $d↓k ≥ \sqrt{N}$.

\algstep A1. [Initialize.] Set $t←0$, $k←0$, $n←N$.\xskip (During this algorithm
the variables $t$, $k$, $n$ are related by the following condition: ``$n=
N\!/p↓1\ldotsm p↓t$, and $n$ has no prime factors less than $d↓k$.'')

\topinsert{\vskip47mm
\ctrline{\caption Fig.\ 10. A simple factoring algorithm.}}

\algstep A2. [$n=1$?] If $n=1$, the algorithm terminates.

\algstep A3. [Divide.] Set $q←\lfloor n/d↓k\rfloor$, $r←n\mod d↓k$.\xskip (Here
$q$ and $r$ are the quotient and remainder obtained when $n$ is divided by $d↓k$.)

\algstep A4. [Zero remainder?] If $r≠0$, go to step A6.

\algstep A5. [Factor found.] Increase $t$ by 1, and set $p↓t←d↓k$, $n←q$. Return
to step A2.

\algstep A6. [Low quotient?] If $q>d↓k$, increase $k$ by 1 and return to step A3.

\algstep A7. [$n$ is prime.] Increase $t$ by 1, set $p↓t←n$, and terminate the
algorithm.\quad\blackslug

\yyskip As an example of Algorithm A\null, consider the factorization of the
number $N = 25852$. We
immediately find that $N = 2 \cdot 12926$; hence $p↓1 = 2$.
Fur\-ther\-more, $12926 = 2 \cdot 6463$, so $p↓2 = 2$. But now $n
= 6463$ is not divisible by 2, 3, 5, $\ldotss$,↔19; we find that
$n = 23 \cdot 281$, hence $p↓3 = 23$. Finally $281 = 12 \cdot
23 + 5$ and $12 ≤ 23$; hence $p↓4 = 281$. The determination of
25852's factors has therefore involved a total of 12 division operations; on the
other hand, if we had tried to factor the slightly smaller number
25849 (which is prime), at least 38 division operations would have been
performed. This illustrates the fact that Algorithm↔A requires
a running time roughly proportional to $\max(p↓{t-1},\sqrt{p↓t}\,)$.\xskip
(If $t=1$, this
formula is valid if we adopt the convention $p↓0=1$.)

The sequence $d↓0$, $d↓1$, $d↓2$, $\ldots$ of
trial divisors used in Algorithm↔A can be taken to
be simply 2, 3, 5, 7, 11, 13, 17, 19,
23, 25, 29, 31, 35, $\ldotss$, where we alternately add 2 and
4 after the first three terms. This sequence contains all numbers
that are not multiples of 2 or 3; it also includes numbers
such as 25, 35, 49, etc., which are not prime, but the algorithm
will still give the correct answer. A further savings of 20
percent in computation time can be made by removing the numbers
$30m \pm 5$ from the list for $m ≥ 1$, thereby eliminating all
of the spurious multiples of 5. The exclusion of multiples of↔7
shortens the list by 14 percent more, etc. A compact bit table
can be used to govern the choice of trial divisors.

If $N$ is known to be small, it is reasonable to have a table of all the
necessary primes as part of the program. For example, if $N$ is less than a
million, we need only include the 168 primes less than a thousand (followed
by the value $d↓{168}=1000$, to terminate the list in case $N$ is a prime larger
than $997↑2$). Such a table can be set up by means of a short auxiliary program,
which builds the table just after the factoring program has been loaded into the
computer; see Algorithm 1.3.2P\null, 
or see exercise↔8.

How many trial divisions are necessary
in Algorithm↔A\null? Let $π(x)$ be the number of primes $≤ x$, so
that $π(2) = 1$, $π(10) = 4$; the asymptotic behavior of this
function has been studied extensively by many of the world's
greatest mathematicians, beginning with \α{Legendre} in 1798. Numerous
advances made during the nineteenth century culminated in 1899, when Charles
\α{de la Vall\'ee Poussin} proved that, for some $A > 0$,
\inx{Vall\'ee Poussin}
\inxf{prime number theorem}
\inxf{primes, distribution of}
$$π(x) = \int ↑{x}↓{2} {dt\over\ln t} + O\biglp
xe↑{-A\sqrt{\,\log x}\,}\bigrp.\eqno(3)$$
[{\sl M\'em.\ Couronn\'es Acad.\ Roy.\ Belgique
\bf 59} (1899), 1--74.]\xskip Integrating by parts yields
$$π(x)={x\over\ln x}+{x\over(\ln x)↑2}+{2!\,x\over(\ln x)↑3}+\cdots
+{r!\,x\over(\ln x)↑{r+1}} + O\left(x\over(\log x)↑{r+2}\right)\eqno(4)$$
for all fixed $r ≥ 0$. The error term in (3) has subsequently been improved;
for example, it can be replaced by
$O\biglp x\exp\biglp-A(\log x)↑{3/5}/(\log
\log x)↑{1/5}\bigrp\bigrp$.\xskip[See A. \α{Walfisz,} {\sl \α{Weyl}'sche Exponential\-summen
\inx{exponential sums}
in der neueren Zahlentheorie} (Berlin, 1963), Chapter↔5.]\xskip Bernhard \β{Riemann}
conjectured in 1859 that
$$\quad π(x) = \sum ↓{k≥1}\mu(k)L\biglp\spose{\raise5pt\hbox
{\hskip2.5pt$\scriptscriptstyle k$}}\sqrt x\,\bigrp/k + O(1) = L(x) -
{1\over 2}L\biglp\sqrt{x}\,\bigrp- {1\over 3}L\biglp\spose{\raise5pt\hbox
{\hskip2.5pt$\scriptscriptstyle 3$}}\sqrt{x}\,\bigrp + \cdots\eqno (5)$$
where $L(x)=\int↓2↑x\,dt/\!\ln t$, and
his formula agrees well with actual counts when $x$ is of reasonable size.
For example, we have the following table:
$$\vbox{\halign{$\hfill#$⊗\quad$\hfill#$⊗\quad$\hfill#$⊗\quad$\hfill#$⊗\quad
\hfill#\cr
x⊗\9π(x)\quad⊗\9x/\!\ln x\quad⊗\9L(x)\quad⊗Reimann's formula\cr
\noalign{\vskip 2pt}
10↑3⊗168⊗144.8⊗176.6⊗168.36\cr
10↑6⊗78498⊗72382.4⊗78626.5⊗78527.40\cr
10↑9⊗50847534⊗48254942.4⊗50849233.9⊗50847455.43\cr}}$$
However, the distribution of large primes is not that simple, and
Riemann's conjecture (5) was disproved by J. E.
\α{Littlewood} in 1914; see \α{Hardy} and Littlewood, {\sl Acta Math.\ \bf 41}
(1918), 119--196, where it is shown that there is a positive
constant $C$ such that $π(x) > L(x) + C\sqrt{x}\log\log\log
x/\!\log x$ for infinitely many↔$x$. Littlewood's result shows that
prime numbers are inherently somewhat mysterious, and it will be necessary to
develop deep properties of mathematics before their distribution is
really understood. Riemann made
\inx{zeta function}
another much more plausible conjecture, the famous ``\α{Riemann
hypothesis}'' that the complex function $\zeta(z)$ is zero only when the real
part of $z$ is equal to $1\over2$, except in the trivial cases that $z$ is
the negative of an even integer. This
hypothesis, if true, would imply that $π(x) = L(x) + O\biglp\sqrt{x}\log x\bigrp$;
see exercise↔25. Richard \α{Brent} has used a method of D. H. \α{Lehmer} to
verify Riemann's hypothesis computationally for all ``small'' values of $z$,
by showing that $\zeta(z)$ has exactly 75,000,000 zeroes whose imaginary part
is in the range $0<\imag z<32585736.4$; all of these zeroes have $\real z={1\over2}$
and $\zeta↑\prime(z)≠0$.\xskip [{\sl Math.\ Comp.\ \bf33} (1979), 1361--1372.]

In order to analyze the average behavior of Algorithm↔A\null, we would like to
know how large the largest prime factor $p↓t$ will tend to be. This question
was first investigated by Karl \α{Dickman} [{\sl Arkiv f\"or Mat., Astron.,
och Fys.\ \bf 22A}, 10 (1930), 1--14], who studied the probability
that a random integer between 1 and↔$x$ will have its largest
prime factor $≤ x↑α$. Dickman gave a heuristic argument to
show that this probability approaches the limiting value $F(α)$
as $x → ∞$, where $F$ can be calculated from the functional
equation
$$F(α) = \int ↑{α}↓{0}F\left(t\over 1 - t\right)\,{dt\over t},\quad\hbox{for }
0 ≤ α ≤ 1;\qquad F(α) = 1\quad\hbox{for }α ≥ 1.\eqno (6)$$
His argument was essentially this: The number of
integers $≤x$ whose largest prime factor is between $x↑t$ and
$x↑{t+dt}$ is $xF↑\prime(t)\,dt$. The number of primes $p$ in that
range is $π(x↑{t+dt}) - π(x↑t) = π\biglp x↑t +  (\ln x)x↑t\,dt\bigrp -
π(x↑t) = x↑t\,dt/t$. For every such↔$p$, the number of integers $n$ such that
``$np≤x$ and the largest prime factor of $n$ is↔${≤p}$'' is
the number of $n≤x↑{1-t}$ whose largest prime factor is $≤(x↑{1-t})↑{t/(1-t)}$,
namely $x↑{1-t}\,F\biglp t/(1-t)\bigrp$. Hence $xF↑\prime(t)\,dt=(x↑t\,dt/t)\biglp
x↑{1-t}F\biglp t/(1-t)\bigrp\bigrp$, and (6) follows by integration. This
heuristic argument can be made rigorous; V. \α{Ramaswami} [{\sl Bull.\ Amer.\
Math.\ Soc.\ \bf 55} (1949), 1122--1127] showed that the probability in
question for fixed $α$ is $F(α)+ O(1/\!\log x)$, as $x → ∞$,
and many other authors have extended the analysis [see the survey
by Karl K. \α{Norton,} {\sl Memoirs Amer.\ Math.\ Soc.\ \bf 106}
(1971), 9--27].

If ${1\over 2} ≤ α ≤ 1$, formula (6) simplifies to
$$F(α)\, =\,1 - \int ↑1↓αF\left(t\over1-t\right)\,{dt\over t}
\,=\,1-\int↓α↑1{dt\over t}\,=\,1+\ln α.$$
Thus, for example, the probability that a random positive integer $≤x$ has a prime
factor $>\sqrt x$ is $1-F({1\over2})=\ln2$, about 69 percent. In all such cases,
Algorithm↔A must work hard.
%folio 479 galley 5 Tape mostly unreadable. (C) Addison-Wesley 1978	*
The net result of this discussion
is that Algorithm↔A will give the answer rather quickly if we
want to factor a six-digit number; but for large $N$ the amount
of computer time for factorization by trial division will rapidly
exceed practical limits, unless we are unusually lucky.

Later in this section we will see that there are fairly good
ways to determine whether or not a reasonably large number $n$
is prime, without trying all divisors up to $\sqrt{n}$. Therefore
Algorithm↔A would often run faster if we inserted a primality
test between steps A2 and A3; the running time for this improved
algorithm would then be roughly proportional to $p↓{t-1}$, the {\sl
second-largest} prime factor of $N$, instead of to $\max(p↓{t-1},
\sqrt{\chop to 0pt{p↓t}}\,)$. By an argument analogous to Dickman's (see
exercise↔18), we can show that the second-largest prime factor of a random
integer↔$x$ will be $≤x↑β$ with approximate probability $G(β)$,
where
$$G(β) = \int ↑{β}↓{0}\left(G\left(t\over 1-t\right) - F\left(t\over1-t\right)
\right)\,{dt\over t},\quad\hbox{for }0 ≤ β≤\textstyle {1\over 2}.\eqno(7)$$
Clearly $G(β) = 1$ for $β ≥ {1\over 2}$.\xskip
(See Fig.↔11.)\xskip Numerical evaluation of (6) and
(7) yields the following ``percentage points'':
$$\vbox{\ninepoint\baselineskip14pt\halign to size{\hfill$#=$\tabskip0pt plus 10pt
⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill
⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill⊗\hfill#\hfill
\hskip .3em\tabskip0pt\cr
F(α), G(β)⊗.01⊗.05⊗.10⊗.20⊗.35⊗.50⊗.65⊗.80⊗.90⊗.95⊗.99\cr
α⊗.2697⊗.3348⊗.3785⊗.4430⊗.5220⊗.6065⊗.7047⊗.8187⊗.9048⊗.9512⊗.9900\cr
β⊗.0056⊗.0273⊗.0531⊗.1003⊗.1611⊗.2117⊗.2582⊗.3104⊗.3590⊗.3967⊗.4517\cr}}$$
Thus, the second-largest prime factor will be $≤x↑{.2117}$ about half the
time, etc.

\topinsert{\vskip 51mm
\baselineskip11pt\ctrline{\hbox par 205pt{\caption Fig.\ 11. 
Probability distribution functions for the two largest prime factors of a
random integer $≤x$.}}}

The {\sl total number of prime factors}, $t$, has also been intensively
analyzed. Obviously $1≤t≤\lg N$, but these lower and upper bounds are
seldom achieved. It is possible to prove that a randomly chosen
 integer between 1 and $x$
will have $t≤\ln\ln x+c\sqrt{\,\ln\ln x}$ with the limiting probability
$${1\over\sqrt{2π}}\int↓{-∞}↑c e↑{-u↑2/2}\,d↓{\null}u\eqno(8)$$
as $x→∞$, for any fixed $c$. In other words, the distribution of $t$ is
\inx{normal distribution}
essentially normal, with mean and variance $\ln\ln x$; about 99.73 percent of
all the large integers $≤x$ have $|t-\ln\ln x|≤3\sqrt{\,\ln\ln x}$. Furthermore
the average value of $t-\ln\ln x$ is known to be $$\gamma+\sum↓{p\,\,\hbox{\:d
prime}\,}
\biglp\ln(1-1/p)+1/(p-1)\bigrp=1.03465\ 38818\ 97438.$$[Cf.\ G. H. \α{Hardy}
and E. M. \α{Wright,} {\sl Introduction to the Theory of Numbers}, 4th ed.\
(Oxford, 1960), $\section$22.11; see also P. \α{Erd\H os} and M. \α{Kac,} {\sl Amer.\ J.
Math.\ \bf26} (1940), 738--742.]

The size of prime factors has a remarkable connection with \α{permutations}: The
average number of bits in the $k$th largest prime factor of a random $n$-bit
integer is asymptotically the same as the average length of the $k$th largest
cycle of a random $n$-element permutation, as $n→∞$.\xskip [See D. E. \α{Knuth} and
L. \α{Trabb Pardo}, {\sl Theoretical Comp.\ Sci.\ \bf3} (1976), 321--348.]\xskip
It follows that Algorithm↔A usually finds
a few small factors and then begins a long-drawn-out search for the big
ones that are left.

\subsectionbegin{Factoring \`a la Monte Carlo} Near the beginning of
\inxf{Monte Carlo, method for factoring}
\inxf{Rho method, see Monte Carlo method for factoring}
Chapter↔3, we observed that ``a random number generator chosen at random isn't
very random.'' This principle, which worked against us in that chapter, has the
redeeming virtue that it leads to a surprisingly efficient method of
factorization, discovered by J. M. \α{Pollard} [{\sl BIT \bf15} (1975), 331--334].
The number of computational steps in Pollard's method is on the order of
$\sqrt{\chop to 0pt{p↓{t-1}}}$,
so it is significantly faster than Algorithm↔A when $N$
is large. According to (7) and Fig.↔11,
the running time will usually be well under $N↑{1/4}$.

Let $f(x)$ be any polynomial with integer coefficients, and consider the two
sequences defined by
$$x↓0=y↓0=A;\qquad x↓{m+1}=f(x↓m)\mod N,\qquad y↓{m+1}=f(y↓m)\mod p,\eqno(9)$$
where $p$ is any prime factor of $N$. It follows that
$$y↓m=x↓m\mod p,\qquad\hbox{for }m≥1.\eqno(10)$$
Now exercise 3.1--7 shows that we will have $y↓m=y↓{\,l(m)-1}$ for some
$m≥1$, where $l(m)$ is the greatest power of 2 that is $≤m$. Thus $x↓m-x↓{\,l(m)-1}$
will be a multiple of $p$. Furthermore if $f(y)\mod p$ behaves as a \α{random mapping}
from the set $\{0,1,\ldotss,p-1\}$ into itself, exercise 3.1--12 shows that the
average value of the least such $m$ will be of order $\sqrt{\chop to 0pt{p}}$.
In fact, exercise↔4 below shows that this
average value for random mappings is less than $1.625\,Q(p)$, where
the function $Q(p)\approx\sqrt{πp/2}$ was defined in Section 1.2.11.3.
If the different prime divisors of $N$ correspond to different
values of $m$ (as they almost surely will, when $N$ is large), we will be able
to find them by calculating $\gcd(x↓m-x↓{\,l(m)-1},N)$ for $m=1$, 2, 3, $\ldotss$,
until the unfactored residue is prime.

From the theory in Chapter 3, we know that a linear polynomial
$f(x) = ax + c$ will not be sufficiently random for our
purposes. The next-simplest case is quadratic, say $f(x) = x↑2
+ 1$; although we don't {\sl know} that this function is sufficiently
random, our lack of knowledge tends to support the hypothesis
of randomness, and empirical tests show that this $f$ does work
essentially as predicted. In fact, $f$ is probably slightly
{\sl better} than random, since $x↑2 + 1$ takes on only ${1\over2}(p+1)$
distinct values mod $p$. Therefore the following procedure is reasonable:

\algbegin Algorithm B (Monte Carlo factorization).
 This algorithm outputs the prime factors of a given integer $N≥2$, with
high probability, although there is a chance that it will fail.

\algstep B1. [Initialize.] Set $x←2$, $x↑\prime←5$, $k←1$, $l←1$, $n←N$.\xskip
$\biglp$During this algorithm, $n$ is the unfactored part of $N$, and $(x,x↑\prime)$
represents $(x↓{\,l(m)-1}\mod n,\,x↓m\mod n)$ in (9), where $f(x)=x↑2+1$, $A=1$,
$l=l(m)$, and $k=2l-m$.$\bigrp$

\algstep B2. [Test primality.] If $n$ is prime (see the discussion below),
output $n$; the algorithm terminates.

\algstep B3. [Factor found?] Set $g←\gcd(x↑\prime-x,\,n)$. If $g=1$, go on to step
B4; otherwise output $g$. Now if $g=n$, the algorithm terminates (and it has failed,
because we know that $n$ isn't prime). Otherwise set $n←n/g$, $x←x\mod n$,
$x↑\prime←x↑\prime\mod n$, and return to step B2.\xskip (Note that $g$ may not be
prime; this should be tested. In the rare event that $g$ isn't prime, its
prime factors probably won't be determinable with this algorithm unless some
changes are made as discussed below.)

\algstep B4. [Advance.] Set $k←k-1$. If $k=0$, set $x←x↑\prime$, $l←2l$, $k←l$.
Set $x↑\prime←(x↑{\prime\,2}+1)\mod n$ and return to B3.\quad\blackslug

%folio 482 galley 6  Mostly hopeless. (C) Addison-Wesley 1978	*
\yyskip As an example of Algorithm↔B\null, let's try
to factor $N = 25852$ again. The third execution of step B3
will output $g = 4$ (which isn't prime). After six more iterations
the algorithm finds the factor $g = 23$.
Algorithm↔B has not distinguished itself in this example, but of course
it was designed to factor {\sl big} numbers. Algorithm↔A takes
much longer to find large prime factors, but it can't be beat
when it comes to removing the small ones. In practice, we should
run Algorithm↔A awhile before switching over to Algorithm↔B.

We can get a better idea of Algorithm↔B's prowess
by considering the ten largest six-digit primes. The number of iterations, $m(p)$,
that Algorithm↔B needs to find the factor $p$ is given in the following table:
$$\vbox{\ninepoint\baselineskip14pt
\halign to size
{$\hfill#=$\tabskip0pt plus 10pt⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\!
\hfill#⊗\hfill#⊗\hfill#⊗\hfill#⊗\hfill#\tabskip0pt\cr
p⊗999863⊗999883⊗999907⊗999917⊗999931⊗999953⊗999959⊗999961⊗999979⊗999983\cr
m(p)⊗276⊗409⊗2106⊗1561⊗1593⊗1091⊗474⊗1819⊗395⊗814\cr}}$$
Experiments indicate that $m(p)$ has an average value of about
 $2\sqrt{\chop to 0pt{p}}$, and
it never exceeds $12\sqrt{\chop to 0pt{p}}$ when
 $p<1000000$. The maximum $m(p)$ for $p<10↑6$ is
$m(874771)=7685$; and the maximum of $m(p)/\sqrt{\chop to 0pt{p}}$
 occurs when $p=290047$,
$m(p)=6251$. According to these experimental results, almost all 12-digit numbers
can be factored in fewer than 2000 iterations of Algorithm↔B (compared to
roughly 100,000 divisions in Algorithm↔A).

The time-consuming operations in each
iteration of Algorithm↔B are the multiprecision multiplication
and division in step B4, and the gcd in step B3. If the gcd operation
is slow, Pollard suggests gaining speed by accumulating the
product mod $n$ of, say, ten consecutive $(x↑\prime - x)$ values
before taking each gcd; this replaces 90 percent of the gcd
operations by a single multiplication and division while only
slightly increasing the chance of failure. He also suggests
starting with $m=q$ instead of $m=1$ in step B1, where $q$
is, say, ${1\over 10}$ the number of iterations you are planning
to use.

In those rare cases where failure occurs for large $N$, we could try using
$f(x)=x↑2+c$ for some $c≠0$ or 1. The value $c=-2$ should also be avoided,
since the recurrence $x↓{m+1}=x↓m↑2-2$ has solutions of the form $x↓m=r↑{2↑m}+r↑{-
2↑m}$. Other values of $c$ do not seem to lead to simple relationships mod
$p$, and they should all be satisfactory when used with suitable starting values.

\subsectionbegin{Fermat's method} Another approach to the factoring
problem, which was used by Pierre de \β{Fermat} in 1643, is more
suited to finding large factors than small ones.\xskip [Fermat's original
description of his method, translated into English, can be found in L. E. \α{Dickson}'s
monumental {\sl History of the Theory of Numbers} {\bf 1} (New York: Chelsea,
1952), 357.]

Assume that $N = uv$, where $u
≤ v$. For practical purposes we may assume that $N$ is odd; this means that
$u$ and $v$ are odd, and we can let
$$\baselineskip15pt
\rpile{x=(u+v)/2,\cr N=x↑2-y↑2,\cr}\qquad\lpile{y=(v-u)/2,\cr 0≤y<x≤N.\cr}
\eqno\rpile{(11)\cr(12)\cr}$$
Fermat's method consists of searching systematically for values of $x$ and $y$ that
satisfy Eq.\ (12). The following algorithm shows how factoring
can therefore be done {\sl without using any division:}

\algbegin Algorithm C (Factoring by addition and subtraction).
Given an odd number $N$, this algorithm determines the largest
factor of $N$ less than or equal to $\sqrt{N}$.

\algstep C1. [Initialize.] Set $x↑\prime ← 2\lfloor \sqrt{N}\rfloor
+ 1$, $y↑\prime ← 1$, $r ← \lfloor \sqrt{N}\rfloor ↑2 - N$.\xskip (During
this algorithm $x↑\prime$, $y↑\prime$, $r$ correspond respectively
to $2x + 1$, $2y + 1$, $x↑2 - y↑2 - N$ as we search for a solution
to (12); we will have $|r| < x↑\prime$ and $y↑\prime < x↑\prime$.)

\algstep C2. [Test $r$.] If $r≤0$, go to step C4.

\algstep C3. [Step $y$.] Set $r←r-y↑\prime$, $y↑\prime←y↑\prime+2$, and
return to C2.

\algstep C4. [Done?] If $r=0$, the algorithm terminates; we have
$$N=\biglp(x↑\prime-y↑\prime)/2\bigrp\biglp(x↑\prime+y↑\prime-2)/2\bigrp,$$
and $(x↑\prime-y↑\prime)/2$ is the largest factor of $N$ less than or equal to
$\sqrt N$.

\algstep C5. [Step $x$.] Set $r←r+x↑\prime$, $x↑\prime←x↑\prime+2$, and
return to C3.\quad\blackslug

\yyskip
The reader may find it amusing to find the factors of 377 by hand, using this
algorithm. The number of steps needed to find the factors $u$ and $v$ of
$N=uv$ is essentially proportional to $(x↑\prime+y↑\prime-2)/2-\lfloor\sqrt N
\rfloor=v-\lfloor\sqrt N\rfloor$; this can, of course, be a very large
number, although each step can be done very rapidly on most computers. An
improvement that requires only $O(N↑{1/3})$ operations in the worst case has been
developed by R. S. \α{Lehman} [{\sl Math.\ Comp.\ \bf28} (1974), \hbox{637--646}].
%folio 488 galley 7  Total loss. (C) Addison-Wesley 1978	*
It is not quite correct
to call Algorithm↔C ``Fermat's method,'' since Fermat used a somewhat
more streamlined approach. Algorithm↔C's
main loop is quite fast on computers, but it is not very
suitable for hand calculation. Fermat actually did not keep
the running value of $y$; he would look at $x↑2 - N$ and tell
whether or not this quantity was a perfect square by looking at
its least significant digits.\xskip (The last two digits of a \α{perfect
square} must be 00, $e1$, $e4$, 25, $o6$, or $e9$, where $e$ is an even digit
and $o$ is an odd digit.)\xskip Therefore he avoided
the operations of steps C2 and C3, replacing them by an occasional
determination that a certain number is not a perfect square.

Fermat's method of looking at the rightmost digits can,
of course, be generalized by using other moduli. Suppose for
clarity that $N = 11111$, and consider the following table:
$$\vbox{\ninepoint\halign to size{\hfill#\tabskip0pt plus 10pt
⊗$#\hfill$⊗$#\hfill$⊗$#\hfill$\tabskip0pt\cr
$m$⊗\hbox{if $x\mod m$ is}⊗\hbox{then $x↑2\mod m$ is}⊗\hbox{and $(x↑2-N)
\mod m$ is}\cr\noalign{\vskip3pt}
3⊗0, 1, 2⊗0, 1, 1⊗1, 2, 2\cr
5⊗0, 1, 2, 3, 4⊗0, 1, 4, 4, 1⊗4, 0, 3, 3, 0\cr
7⊗0, 1, 2, 3, 4, 5, 6⊗0, 1, 4, 2, 2, 4, 1⊗5, 6, 2, 0, 0, 2, 6\cr
8⊗0, 1, 2, 3, 4, 5, 6, 7⊗0, 1, 4, 1, 0, 1, 4, 1⊗1, 2, 5,2,1,2,5,2\cr
11⊗0,1,2,3,4,5,6,7,8,9,10⊗0,1,4,9,5,3,3,5,9,4,1⊗10,0,3,8,4,2,2,4,8,3,0\cr}}$$
If $x↑2 - N$ is to
be a perfect square $y↑2$, it must have a residue mod $m$ consistent
with this fact, for all $m$. For example, if $N=11111$ and $x \mod 3 ≠ 0$,
then $(x↑2 - N)\mod 3 = 2$, so $x↑2 - N$ cannot
be a perfect square; therefore $x$ must be a multiple of 3 whenever
$11111 = x↑2 - y↑2$. The table tells us, in fact, that
$$\vcenter{\halign{$x\mod #\hfill=\null$⊗#\hfill\cr
3⊗0;\cr
5⊗0, 1, or 4;\cr
7⊗2, 3, 4, or 5;\cr
8⊗0 or 4 (hence $x \mod 4 = 0$);\cr
11⊗1, 2, 4, 7, 9, or 10.\cr}}\eqno(13)$$
This narrows down the search for $x$ considerably. For
example, $x$ must be a multiple of 12. We must have $x ≥ \lceil
\sqrt{N}\,\rceil = 106$, and it is easy to verify that the first
value of $x ≥ 106$ that satisfies all of the conditions in
(13) is $x = 144$. Now 144$↑2 - 11111 = 9625$, and by attempting to take
the square root of 9625 we find that it is not a square. The first
value of $x > 144$ that satisfies (13) is $x= 156$. In this
case $156↑2 - 11111 =13225=115↑2$; so we have found the desired solution $x
= 156$, $y = 115$. This calculation shows that $11111 = 41 \cdot
271$.

The hand calculations involved in the above example are comparable
to the amount of work required to divide 11111 by 13, 17, 19,
23, 29, 31, 37, and 41, even though the factors 41 and 271 are
not very close to each other; thus we can see the advantages
of Fermat's method.

In place of the moduli considered in (13), we can use any powers of distinct primes.
For example, if we had used 25 in place of 5, we would find
that the only permissible values of $x\mod 25$ are 0, 5, 6, 10, 15, 19, and 20.
This gives more information than (13). In general, we will get more information
modulo↔$p↑2$ than we do modulo $p$, for odd primes $p$, whenever $x↑2-N≡0\modulo p$ has
a solution $x$.

The modular method just used is called a
{\sl \β{sieve procedure}}, since we can imagine passing all integers
through a ``sieve'' for which only those values with $x\mod 3=0$
come out, then sifting these numbers through another sieve that allows only
numbers with $x\mod5=0$, 1, or 4 to pass, etc. Each sieve by itself will
remove about half of the remaining values (see exercise↔6); and when
we sieve with respect to moduli that are relatively prime in
pairs, each sieve is independent of the others because of the
Chinese remainder theorem (Theorem↔4.3.2C\null). So if we sieve with
respect to, say, 30 different primes, only about one value in
every $2↑{30}$ will need to be examined to see if $x↑2 - N$ is
a perfect square $y↑2$.

\algbegin Algorithm D (Factoring with sieves). Given an
odd number $N$, this algorithm determines the largest factor
of $N$ less than or equal to $\sqrt{N}$. The procedure uses
moduli $m↓1$, $m↓2$, $\ldotss$, $m↓r$ that are relatively prime
to each other in pairs and rel\-atively prime to $N$. We assume
that $r$ ``sieve tables'' $S[i,j]$ for $0 ≤ j < m↓i$, $1 ≤
i ≤ r$, have been prepared, where
$$\baselineskip14pt
S[i, j] = \left\{\vcenter{\halign{#,\qquad⊗#\hfill\cr
1⊗if $j↑2-N≡y↑2\modulo{m↓i}$ has a solution $y$;\cr
0⊗otherwise.\cr}}\right.$$

\algstep D1. [Initialize.] Set $x←\lceil\sqrt{N}\,\rceil
$, and set $k↓i ← (-x)\mod m↓i$ for $1 ≤ i ≤ r$.\xskip (Throughout this
algorithm the index variables $k↓1$, $k↓2$, $\ldotss$, $k↓r$ will
be set so that $(-x) \mod m↓i = k↓i$.)

\algstep D2. [Sieve.] If $S[i, k↓i]=1$ for $1≤i≤r$, go to step D4.

\algstep D3. [Step $x$.] Set $x ← x+1$, and set $k↓i←(k↓i-1)\mod m↓i$ for
$1 ≤ i ≤ r$. Return to step D2.

\algstep D4. [Test $x↑2 - N$.] Set $y ← \lfloor \sqrt{x↑2 -
N}\rfloor$ or to $\lceil \sqrt{x↑2 - N}\,\rceil $. If $y↑2 =
x↑2 - N$, then $(x - y)$ is the desired factor, and the algorithm
terminates. Otherwise return to step D3.\quad\blackslug

\yyskip There
are several ways to make this procedure run fast. For example,
we have seen that if $N \mod 3 = 2$, then $x$ must be a multiple
of 3; we can set $x = 3x↑\prime $, and use a different sieve
corresponding to $x↑\prime $, increasing the speed threefold.
If $N\mod 9 = 1$, 4, or 7, then $x$ must be congruent respectively to
$\pm1$, $\pm2$, or $\pm4\modulo 9$; so we run two sieves (one for $x↑\prime$ and one
for $x↑{\prime\prime}$, where $x=9x↑\prime+a$ and $x=9x↑{\prime\prime}-a$) to
increase the speed by a factor of 4$1\over2$. If $N\mod4=3$, then $x\mod4$ is known
and the speed is increased by an additional
factor of 4; in the other case, when $N\mod 4 = 1$, $x$ must
be odd so the speed may be doubled. Another way to double the
speed of the algorithm (at the expense of storage space) is to combine pairs of
moduli, using $m↓{r-k\,}m↓k$ in place of $m↓k$ for $1≤k<{1\over2}r$.

An even more important method of speeding up Algorithm↔D is to use the
``\α{Boolean operations}'' found on most binary computers. Let us assume, for
\inx{logical operations}
example, that \α{\MIX}\ is a binary computer with 30 bits per word. The tables
$S[i,k↓i]$ can be kept in memory with one bit per entry; thus 30 values can
be stored in a single word. The operation \.{\α{AND}}, which replaces the $k$th bit
of the accumulator by zero if the $k$th bit of a specified word in memory is
zero, for $1≤k≤30$, can be used to process 30 values of $x$ at once! For
convenience, we can make several copies of the tables $S[i,j]$ so that the
table entries for $m↓i$ involve $\lcm(m↓i,30)$ bits; then the sieve tables for
each modulus fill an integral number of words. Under these assumptions, 30
executions of the main loop in Algorithm↔D are equivalent to code of the
following form:

{\yyskip\tabskip 60pt\mixthree{\!
D2⊗LD1⊗K1⊗$\rI1←k↓1↑\prime$.\cr
⊗LDA⊗S1,1⊗$\rA←S↑\prime[1,rI1]$.\cr
⊗DEC1⊗1⊗$\rI1←\rI1-1.$\cr
\\⊗J1NN⊗*+2\cr
⊗INC1⊗M1⊗If $\rI1<0$, set $\rI1←\rI1+\lcm(m↓1,30)$.\cr
⊗ST1⊗K1⊗$k↓1↑\prime←\rI1$.\cr
\\⊗LD1⊗K2⊗$\rI1←k↓2↑\prime$.\cr
⊗AND⊗S2,1⊗$\rA←\rA∧S↑\prime[2,\rI1]$.\cr
⊗DEC1⊗1⊗$\rI1←\rI1-1$.\cr
⊗J1NN⊗*+2\cr
⊗INC1⊗M2⊗If $\rI1<0$, set $\rI1←\rI1+\lcm(m↓2,30)$.\cr
⊗ST1⊗K2⊗$k↓2↑\prime←\rI1$.\cr
\\⊗LD1⊗K3⊗$\rI1←k↓3↑\prime$.\cr
⊗$\cdots$⊗⊗($m↓3$ through $m↓r$ are like $m↓2$)\cr
⊗ST1⊗Kr⊗$k↓r↑\prime←\rI1$.\cr
\\⊗INCX⊗30⊗$x←x+30$.\cr
⊗JAZ⊗D2⊗Repeat if all sieved out.\quad\blackslug\cr}}

\yyskip\noindent
The number of cycles for 30 iterations is essentially $2+8r$; if $r=11$ this
means three cycles are being used on each iteration, just as in Algorithm↔C\null,
and Algorithm↔C involves $y={1\over2}(v-u)$ more iterations.
%folio 492 galley 8  Bad spots. (C) Addison-Wesley 1978		*

If the table entries for $m↓i$ do
not come out to be an integral number of words, further shifting
of the table entries would be necessary on each iteration in order to
align the bits properly. This would add quite a lot
of coding to the main loop and it would probably make the program
too slow to compete with Algorithm↔C unless $v/u ≤ 100$ (see
exercise↔7).

Sieve procedures can be applied to a variety of other problems,
not necessarily having much to do with arithmetic. A survey
of these techniques has been prepared by Marvin C. \α{Wunderlich},
{\sl JACM} {\bf 14} (1967), 10--19.

Special sieve machines (of reasonably low cost) have been constructed
by D.↔H. \α{Lehmer} and his associates over a period of many years;
see, for example, {\sl AMM} {\bf 40} (1933), 401--406. Lehmer's
electronic delay-line sieve, which began operating in 1965, processes
one million numbers per second. Thus, each iteration of the
loop in Algorithm↔D can be performed in one microsecond on this
device. Another way to factor with sieves is described by D. H. and
\inx{Lehmer, Emma}
Emma Lehmer in {\sl Math.\ Comp.\ \bf 28} (1974), 625--635.

\subsectionbegin{Primality testing} None of the algorithms
\inxf{prime numbers, verifying primality}
we have discussed so far is an efficient way to determine that
a large number $n$ is prime. Fortunately, there are other methods
available for settling this question; efficient methods
have been devised by \'E. \α{Lucas} and others,
notably D. H. \α{Lehmer} [see {\sl Bull.\ Amer.\ Math.\ Soc.\ \bf 33}
(1927), 327--340].

According to \α{Fermat's theorem} (Theorem
1.2.4F\null), we have $x↑{p-1}\mod p = 1$ whenever $p$ is prime and  $x$ is
not a multiple of $p$. Furthermore, there are efficient ways
to calculate $x↑{n-1}\mod n$, requiring only $O(\log n)$
operations of multiplication mod $n$.\xskip (We shall study these
in Section 4.6.3 below.)\xskip Therefore we can often determine that
$n$ is {\sl not} prime when this relationship fails.

For example,
\α{Fermat} once verified that the numbers $2↑1 + 1$, $2↑2 + 1$, $2↑4 + 1$,
$2↑8 + 1$, and $2↑{16} + 1$ are prime. In a letter to \α{Mersenne} written
in 1640, Fermat conjectured that $2↑{2↑n}+ 1$ is always
prime, but said he was unable to determine definitely whether
the number $4294967297 = 2↑{32} + 1$ is prime or not. Neither Fermat nor Mersenne
ever resolved this problem, although they could have done it as follows: The
number $3↑{2↑{32}}\mod(2↑{32}+1)$ can be computed by doing 32 operations of squaring
modulo $2↑{32}+1$, and the answer is 3029026160; therefore (by Fermat's
own theorem, which he discovered in the
same year 1640!) the number $2↑{32} + 1$ is {\sl not} prime. This
argument gives us absolutely no idea what the factors are, but
it answers Fermat's question.

Fermat's theorem is a powerful test for showing non-primality of a given number.
When $n$ is not prime, it is always possible to
find a value of $x < n$ such that $x↑{n-1} \mod n ≠ 1$; experience
shows that, in fact, such a value can almost always be found very
quickly. There are some rare values of $n$ for which $x↑{n-1}
\mod n$ is frequently equal to unity, but then $n$ has a factor
less than $\spose{\raise5pt\hbox{\hskip2.5pt$\scriptscriptstyle3$}}\sqrt n$;
see exercise↔9. 

The same method can be extended to prove that a large prime
number $n$ really {\sl is} prime, by using the following idea:
{\sl If there is a number $x$ for which the order of $x$ modulo
$n$ is equal to $n - 1$, then $n$ is prime.}\xskip (The \α{order of $x$ modulo
$n$} is the smallest positive integer $k$ such that $x↑k \mod
n = 1$; see Section 3.2.1.2.)\xskip For this condition implies that
the numbers $x↑k \mod n$ for $1 ≤ k ≤ n - 1$ are distinct and
relatively prime to $n$, so they must be the numbers 1, 2, $\ldotss$,
$n - 1$ in some order; thus $n$ has no proper divisors. If $n$
is prime, such a number $x$ (called a ``primitive root'' of $n$) will
always exist; see exercise 3.2.1.2--16. In fact,
primitive roots are rather numerous. There are $\varphi
(n - 1)$ of them, and this is quite a substantial number, since
$n/\varphi(n-1)= O(\log\log n)$.

It is unnecessary to calculate $x↑k \mod n$ for all $k ≤
n - 1$ to determine if the order of $x$ is $n - 1$ or not. The
order of $x$ will be $n - 1$ if and only if
$$\hbox to size{\vbox{\baselineskip14pt\halign{\qquad\hfill#⊗ $#\hfill$\cr
i)⊗x↑{n-1}\mod n=1;\cr
ii)⊗x↑{(n-1)/p}\mod n≠1\hbox{ for all primes $p$ that divide $n - 1$.}\cr}}\hfil}$$
For $x↑s\mod n=1$ if and only if $s$ is
a multiple of the order of $x$ modulo $n$. If the two
conditions hold, and if $k$ is the order of $x$ modulo $n$,
we therefore know that $k$ is a divisor of $n - 1$, but not
a divisor of $(n - 1)/p$ for any prime factor $p$ of $n - 1$;
the only remaining possibility is $k=n - 1$. This completes the proof that
conditions (i) and (ii) suffice to establish the primality of $n$.

Exercise 10 shows that we can in fact use
different values of $x$ for each of the primes $p$, and $n$ will still
be prime. We may restrict consideration to prime values of $x$, since
the order of $uv$ modulo $n$ divides the least common multiple
of the orders of $u$ and $v$ by exercise↔3.2.1.2--15. Conditions
(i) and (ii) can be tested efficiently by using the rapid methods
for evaluating powers of numbers discussed in Section 4.6.3.
But it is necessary to know the prime factors of $n - 1$, so
we have an interesting situation in which the factorization
of $n$ depends on that of $n - 1!$

\subsectionbegin{An example} The study of a reasonably typical
large factorization will help to fix the ideas we have discussed
so far. Let us try to find the prime factors of $2↑{214}+1$, a 65-digit
number. The factorization can be initiated with a bit of clairvoyance
if we notice that $$2↑{214} + 1 = (2↑{107} - 2↑{54}
+ 1)(2↑{107} + 2↑{54} + 1);\eqno (14)$$
this identity is a special case of some factorizations
discovered by A. \α{Aurifeuille} in 1873 [see \α{Dickson}'s {\sl History},
{\bf 1}, p.\ 383]. The problem now boils down to examining each of the
33-digit factors in (14).

A computer program readily discovers that
$2↑{107} - 2↑{54} + 1 = 5 \cdot 857 \cdot n↓0$, where
$$n↓0 =37866809061660057264219253397\eqno(15)$$
is a 29-digit number having no prime factors less than 1000.
A multiple-precision calculation using the ``binary method'' of
Section 4.6.3 shows that
$$3↑{n↓0-1}\mod n↓0 = 1,$$
so we suspect that $n↓0$ is prime. It is certainly
out of the question to prove that $n↓0$ is prime by trying the
10 million million or so potential divisors, but the method discussed above
gives a feasible test for primality: our next goal is to factor $n↓0-1$. With little
difficulty, our computer will tell us that
$$n↓0-1 = 2 \cdot 2 \cdot 19 \cdot 107 \cdot 353 \cdot
n↓1,\qquad n↓1 = 13191270754108226049301.$$
Here $3↑{n↓1-1}\mod n↓1≠1$, so $n↓1$ is not prime; by continuing
Algorithm↔A or Algo\-rithm↔B we find $$n↓1 = 91813 \cdot n↓2,\qquad n↓2
= 143675413657196977.$$This time $3↑{n↓2-1}\mod n↓2
= 1$, so we will try to prove that $n↓2$ is prime. This requires
the factorization $n↓2 - 1 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot
3 \cdot 3 \cdot 547 \cdot n↓3$, where $n↓3 = 1824032775457$. Since $3↑{n↓3-1}
\mod n↓3 ≠ 1$, we know that $n↓3$ is composite, and
Algorithm↔A finds that $n↓3 = 1103 \cdot n↓4$, where $n↓4 = 1653701519$.
The number $n↓4$ behaves like a prime (i.e., $3↑{n↓4-1}
\mod n↓4 = 1)$, so we calculate
$$n↓4 - 1 = 2 \cdot 7 \cdot 19 \cdot 23 \cdot 137 \cdot 1973.$$
Good; this is our first complete factorization. We are now
ready to backtrack to the previous subproblem, proving that
$n↓4$ is prime. Using the procedure suggested by exercise↔10, we compute
the following values:
$$\vcenter{\halign{$\ctr{#}$⊗\qquad$\rt{#}$⊗\qquad$\ctr{#}$⊗\qquad$\ctr{#}$\cr
x⊗p⊗x↑{(n↓4-1)/p}\mod n↓4⊗x↑{n↓4-1}\mod n↓4\cr
\noalign{\vskip 3pt}
2⊗2⊗1⊗(1)\cr
2⊗7⊗766408626⊗(1)\cr
2⊗19⊗332952683⊗(1)\cr
2⊗23⊗1154237810⊗(1)\cr
2⊗137⊗373782186⊗(1)\cr
2⊗1973⊗490790919⊗(1)\cr
3⊗2⊗1⊗(1)\cr
5⊗2⊗1⊗(1)\cr
7⊗2⊗1653701518⊗1\cr}}\eqno(16)$$
(Here ``(1)'' means a result of 1 that needn't
be computed since it can be deduced from previous calculations.)
Thus $n↓4$ is prime, and $n↓2 - 1$ has been completely factored.
A similar calculation shows that $n↓2$ is prime, and this complete
factorization of $n↓0 - 1$ finally shows [after still another
calculation like (16)] that $n↓0$ is prime.

The last three lines of (16) represent a search for an integer $x$ that
satisfies $x↑{(n↓4-1)/2}\not≡x↑{n↓4-1}≡1\modulo{n↓4}$. If $n↓4$ is prime,
we have only a 50-50 chance of success, so the case $p=2$ is typically the
hardest one to verify. We could streamline this part of the calculation
by using the law of \α{quadradic reciprocity} (cf.\ exercise 23), which tells
us for example that $5↑{(q-1)/2}≡1\modulo q$ whenever $q$ is a prime congruent
to $\pm1\modulo5$. Merely calculating $n↓4\mod5$ would have told us right away
that $x=5$ could not possibly help in showing that $n↓4$ is prime. In fact,
however, the result of exercise↔26 implies that the case $p=2$ doesn't really
need to be considered at all when testing $n$ for primality, unless $n-1$ is
divisible by a high power of↔2, so we could have dispensed with the last
three lines of (16) entirely.

The next quantity to be factored is the other half of (14), namely
$$n↓5= 2↑{107} + 2↑{54} + 1.$$
Since $3↑{n↓5-1}\mod n↓5 ≠ 1$, we know
that $n↓5$ is not prime, and Algorithm↔B shows that $n↓5 = 843589
\cdot n↓6$, where $n↓6 = 192343993140277293096491917$. Unfortunately,
$3↑{n↓6-1} \mod n↓6 ≠ 1$, so we are left with a 27-digit
nonprime. Con\-tinuing Algorithm↔B might well exhaust our
patience (not our budget---nobody is paying for this, we're
using idle time on a weekend rather than ``prime time'').
 But the sieve method of Algorithm↔D
will be able to crack $n↓6$ into its two factors,
$$n↓6=8174912477117\cdot23528569104401.$$
This result could {\sl not} have been discovered by Algorithm↔A in a
reasonable length of time.\xskip (A few million iterations of Algorithm↔B would
probably have sufficed.)

Now the computation is complete: $2↑{214}+1$ has the prime factorization
$$5 \cdot 857 \cdot 843589 \cdot 8174912477117 \cdot 23528569104401
\cdot n↓0,$$
where $n↓0$ is the 29-digit prime in (15). A certain
amount of good fortune entered into these calculations, for
if we had not started with the known factorization (14) it is
quite probable that we would first have cast out the small factors,
reducing $n$ to $n↓6n↓0$. This 55-digit number would have
been much more difficult to factor---Algorithm↔D would be useless
and Algorithm↔B would have to work overtime because of the high
precision necessary.

Dozens of further numerical examples can
be found in an article by John \α{Brillhart} and J. L. \α{Selfridge},
{\sl Math.\ Comp.\ \bf 21} (1967), 87--96.
%folio 496 galley 9  Bad spots. (C) Addison-Wesley 1978	*
\subsectionbegin{Improved primality tests} Since the
above procedure for proving that $n$ is prime requires the complete
factorization of $n - 1$, it will bog down for large $n$. Another
technique, which uses the factorization of $n + 1$ instead,
is described in exercise↔15; if $n - 1$ turns out to be too
hard, $n + 1$ might be easier.

Significant improvements are available for dealing with large $n$. For example,
it is not difficult to prove a stronger converse of Fermat's theorem that
requires only a partial factorization of $n-1$. Exercise↔26 shows that we could
have avoided most of the calculations in (16); the three conditions
$2↑{n↓4-1}\mod n↓4=\gcd(2↑{(n↓4-1)/23}-1,n↓4)=\gcd(2↑{(n↓4-1)/1973}-1,n↓4)=1$
are sufficient by themselves to prove that $n↓4$ is prime. \α{Brillhart},
\α{Lehmer,} and \α{Selfridge}
 have in fact developed a method that works when the numbers
$n - 1$ and $n + 1$ have been only partially factored
 [{\sl Math.\ Comp.\ \bf 29} (1975), 620--647, Corollary↔11]:
 Suppose $n-1=f↑{\scriptscriptstyle-}r↑{\scriptscriptstyle-}$ and
$n+1=f↑{\scriptscriptstyle+}r↑{\scriptscriptstyle+}$, where we know
the complete factorizations of $f↑{\scriptscriptstyle-}$ and
 $f↑{\scriptscriptstyle+}$, and we also know that
all factors of $r↑{\scriptscriptstyle-}$ and $r↑{\scriptscriptstyle+}$ are $≥b$.
 If the product $\biglp
b↑3f↑{\scriptscriptstyle-}f↑{\scriptscriptstyle+}\max(f↑{\scriptscriptstyle-},
f↑{\scriptscriptstyle+})\bigrp$ is greater than $2n$, a small amount of additional computation,
described in their paper, will determine whether or not $n$
is prime. Therefore numbers of up to 35 digits can usually
be tested for primality in 2 or 3 seconds, simply by casting
out all prime factors $<30030$ from $n\pm 1$ [see J. L. Selfridge
and M. C. \α{Wunderlich,} {\sl Proc. Fourth Manitoba Conf. Numer.
Math.} (1974), 109--120]. The partial factorization of other
quantities like $n↑2 \pm n +1$ and $n↑2+1$ can be used to improve this method
still further [see H. C. \α{Williams} and J. S. \α{Judd,} {\sl Math.\ Comp.\ \bf30}
(1976), 157--172, 867--886].

In practice, when $n$ has no small prime
factors and $3↑{n-1}\mod n = 1$, it has almost always turned
out that $n$ is prime.\xskip $\biglp$One of the rare exceptions in the
author's experience is $n={1\over7}(2↑{28}-9)=2341\cdot16381$.$\bigrp$\xskip
On the other hand, some nonprime values of $n$ are definitely bad news for the
primality test we have discussed, because it might happen that $x↑{n-1}\mod n=1$
for all $x$ relatively prime to $n$ (see exercise↔9). One such number is
$n = 3 \cdot 11 \cdot 17 = 561$; here $λ(n) = \lcm(2, 10, 16)
= 80$ in the notation of Eq.\ 3.2.1.2--9, so $x↑{80}\mod 561 =
1 = x↑{560}\mod 561$ whenever $x$ is relatively prime to 561.
Our procedure would repeatedly fail to show that such an $n$ is prime, until we
had stumbled across one of its divisors. To improve the method, we need a
quick way to determine the nonprimality of nonprime $n$, even in such
pathological cases.

The following surprisingly
simple procedure is guaranteed to do the job with high probability:

\algbegin Algorithm P (Probabilistic primality test). Given an odd integer $n$,
this algorithm attempts to decide whether or not $n$ is prime. By repeating
\inxf{probabilistic algorithms}
\inxf{random numbers, using, see also probabilistic algorithms}
the algorithm several times, as explained in the remarks below, it is possible to
be extremely confident about the primality of $n$, in a precise sense, yet the
primality will not be rigorously proved. Let $n=1+2↑kq$, where $q$ is odd.

\algstep P1. [Generate $x$.] Let $x$ be a random integer in the range $1<x<n$.

\algstep P2. [Exponentiate.] Set $j←0$ and $y←x↑q\mod n$.\xskip (As in our previous
primality test, $x↑q\mod n$ should be calculated in $O(\log q)$ steps, cf.\
Section 4.6.3.)

\algstep P3. [Done?] (Now $y=x↑{2↑jq}\mod n$.)\xskip
If $j=0$ and $y=1$, or if $y=n-1$, terminate the algorithm
and say ``$n$ is probably prime.'' If $j>0$ and $y=1$, go to step P5.

\algstep P4. [Increase $j$.] Increase $j$ by 1. If $j<k$, set $y←y↑2\mod n$ and
return to step P3.

\algstep P5. [Not prime.] Terminate the algorithm and say ``$n$ is definitely
not prime.''\quad\blackslug

\yyskip The idea underlying Algorithm P is that if $n=1+2↑kq$ is prime and
$x↑q\mod n≠1$, the sequence of values
$$x↑q\mod n,\quad
x↑{2q}\mod n,\quad x↑{4q}\mod n,\quad\ldotss,\quad x↑{2↑kq}\mod n$$
will end with↔1, and the value just preceding the first appearance of 1 will be
$n-1$.\xskip$\biglp$The only solutions to $y↑2≡1\modulo p$ are $y≡\pm1$, when $p$
is prime, since $(y-1)(y+1)$ must be a multiple of $p$.$\bigrp$

Exercise 22 proves the basic fact that Algorithm↔P will be wrong at most $1\over4$
of the time, for all $n$. Actually it will rarely fail at all, for most $n$;
but the crucial point is that the probability of failure is bounded {\sl
regardless} of the value of $n$.

Suppose we invoke Algorithm↔P repeatedly, choosing $x$ independently and at random
whenever we get to step P1. If the algorithm ever reports that $n$ is nonprime,
we can say that $n$ definitely isn't prime. But if the algorithm reports 25
times in a row that $n$ is ``probably prime,'' we can say that $n$ is ``almost
surely prime.'' For the probability is less than $(1/4)↑{25}$ that such a
25-times-in-a-row procedure gives the wrong information about $n$. This is less
than one chance in a quadrillion; even if we certified a billion different primes
with such a procedure, the expected number of mistakes would be less than
$1\over1000000$. It's much more likely that our computer has dropped a bit in its
calculations, due to hardware malfunctions or cosmic radiations, than that
Algorithm↔P has repeatedly guessed wrong!

Probabilistic algorithms like this lead us to question our traditional standards
of reliability. Do we really {\sl need} to have a rigorous proof of primality?
For people unwilling to abandon traditional notions of proof, Gary L. \β{Miller}
has demonstrated that if $\spose{\raise5pt\hbox{\hskip2.5pt$\scriptscriptstyle r
$}}\sqrt n$ is not an integer for any integer $r≥2$ (this condition being
easily checked), and if a certain well-known conjecture in number theory called
the \α{Extended Riemann Hypothesis} can be proved, then either $n$ is prime or
\inx{Riemann Hypothesis}
there is an $x<4(\ln n)↑2$ such that Algorithm↔P will discover the nonprimality
of $n$.\xskip [See {\sl J. Comp.\ System Sci.\ \bf 13} (1976), 300--317. The
constant↔4 in this upper bound is due to Peter \α{Weinberger,} whose paper on the
subject % to appear
is not yet published.]\xskip Thus, we would have a rigorous way to test primality in
$O(\log n)↑5$ elementary operations, as opposed to a probabilistic method whose
running time is $O(\log n)↑3$. But one might well ask whether any purported
proof of the Extended Riemann Hypothesis will ever be as reliable as repeated
application of Algorithm↔P on random $x$'s.

A probabilistic test for primality was first proposed in 1974 by R. \α{Solovay} and
V. \α{Strassen,} who devised the interesting but more complicated test
described in exercise↔23(b).\xskip[See {\sl SIAM J. Computing \bf 6} (1977), 84--85;
{\bf7} (1978), 118.]\xskip Algorithm↔P is a simplified version of a procedure
due to M. O. \α{Rabin,} based in part on ideas of Gary L. Miller [cf.\ {\sl
Algorithms and Complexity}, ed.\ by J. F. \α{Traub} (New York: Academic Press, 1976),
35--36].

A completely different approach to primality testing was discovered in 1980 by
Leonard M. \α{Adleman}. His highly interesting method is based on the theory of
\α{algebraic integers}, so it is beyond the scope of this book; but it leads to
a non-probabilistic procedure that will decide the primality of any number of
up to, say, 250 digits, in a few hours at most.\xskip[See L. M. Adleman and
R. S. \α{Rumely}, to appear.]

\subsectionbegin{Factoring via \β{continued fractions}} The factorization
procedures we have discussed so far will often balk at numbers
of 30 digits or more, and another idea is needed if we are to
go much further. Fortunately there is such an idea; in fact,
there were two ideas, due respectively to A. M. \α{Legendre} and
M. \α{Kraitchik,} that D. H. \α{Lehmer} and R. E. \α{Powers} used to devise
a new technique many years ago [{\sl Bull.\ Amer.\ Math.\ Soc.\
\bf 37} (1931), 770--776]. However, the method was not used
at the time because it was comparatively unsuitable for desk calculators. This
negative judgment prevailed until the late 1960s, when John \α{Brillhart}
found that the Lehmer--Powers approach deserved to be resurrected,
since it was quite well suited to computer programming. In fact,
he and Michael A. \α{Morrison} later developed it into the
champion of all known methods for factoring large numbers: Their program
would handle
typical 25-digit numbers in about 30 seconds, and 40-digit numbers
in about 50 minutes, on an \α{IBM 360/91 computer} [see {\sl Math.\ Comp.\
\bf 29} (1975), 183--205]. In 1970 the method had its first
triumphant success, discovering that $2↑{128} + 1 = 59649589127497217
\cdot 5704689200685129054721$.

The basic idea is to search for numbers $x$ and $y$ such that
$$\quad x↑2 ≡ y↑2 \modulo N,\qquad 0 < x, y < N,\qquad x ≠ y,\qquad
x + y ≠ N.\eqno (17)$$
Fermat's method imposes the stronger requirement $x↑2-y↑2=N$, but
actually the congruence (17) is enough to split $N$ into factors:
It implies that $N$ is a divisor of $x↑2 - y↑2 = (x - y)(x +
y)$, yet $N$ divides neither $x - y$ nor $x + y$; hence $\gcd(N,
x - y)$ and $\gcd(N, x + y)$ are proper factors of $N$ that
can be found by Euclid's algorithm.

One way to discover solutions of (17) is to look for values of $x$ such that
$x↑2≡a\modulo N$, for small values of $|a|$. As we will see, it is often a simple
matter to piece together solutions of this congruence to obtain solutions of (17).
Now if $x↑2=a+kNd↑2$ for some $k$ and $d$, with small $|a|$, the fraction
$x/d$ is a good approximation to $\sqrt{kN}\,$; conversely, if $x/d$ is an
especially good approximation to $\sqrt{kN}$, the difference $|x↑2-kNd↑2|$ will
be small. This observation suggests looking at the continued fraction expansion
of $\sqrt{kN}$, since we have seen (in Eq.\ 4.5.3--12 and exercise 4.5.3--42)
that continued fractions yield good rational approximations.

Continued fractions for quadratic irrationalities have many pleasant prop\-er\-ties,
which are proved in exercise↔4.5.3--12. The algorithm below makes use of these
properties to derive solutions to the congruence
$$x↑2≡(-1)↑{e↓0}p↓1↑{e↓1}p↓2↑{e↓2}\ldotss p↓m↑{e↓m}\;\modulo N.\eqno(18)$$
Here we use a fixed set of small primes $p↓1=2$, $p↓2=3$, $\ldotss$, up to
$p↓m$; only primes $p$ such that either $p=2$ or $(kN)↑{(p-1)/2}\mod p ≤1$ should
appear in this list, since other primes
will never be factors of the numbers generated by the algorithm
(see exercise↔14). If $(x↓1, e↓{01}, e↓{11}, \ldotss , e↓{m1})$,
$\ldotss$, $(x↓r, e↓{0r}, e↓{1r}, \ldotss , e↓{mr})$ are solutions
of (18) such that the vector sum
$$(e↓{01}, e↓{11}, \ldotss , e↓{m1}) + \cdots + (e↓{0r}, e↓{1r},
\ldotss , e↓{mr}) = (2e↑\prime↓0,2e↑\prime↓1, \ldotss , 2e↑\prime↓m)\eqno(19)$$
is {\sl even} in each component, then
$$x = (x↓1 \ldotsm x↓r)\mod N,\qquad y = \biglp(-1)↑{e↓0↑\prime}p↑{e↓1↑\prime}↓{1}
\ldotss p↑{e↓{\!m}↑\prime}↓{m})\mod N\eqno (20)$$
yields a solution to (17), except for the possibility
that $x ≡ \pm y$. Condition (19) essentially says that the vectors
are linearly dependent modulo 2, so we must have a solution to (19) if we have
found at least $m+2$ solutions to (18).
%folio 500 galley 10  Bad spots. (C) Addison-Wesley 1978	*
\algbegin Algorithm E (Factoring via continued
fractions). Given a positive integer $N$ and a positive integer
$k$ such that $kN$ is not a perfect square, this algorithm attempts
to discover solutions to the congruence (18) for fixed $m$,
by analyzing the convergents to the continued fraction for $\sqrt{kN}$.\xskip
(Another algorithm, which uses the outputs to discover factors
of $N$, is the subject of exercise↔12.)

\algstep E1. [Initialize.] Set $D ← kN$, $R
← \lfloor \sqrt{D}\rfloor$, $R↑\prime ← 2R$, $U ← U↑\prime ←R↑\prime
$, $V ← 1$, $V↑\prime ← D - R↑2$, $P ← R$, $P↑\prime ← 1$, $A ← 0$, $S ←
0$.\xskip (This algorithm follows the general procedure of exercise
4.5.3--12, finding the continued fraction expansion of $\sqrt{kN}$.
The variables $U$, $U↑\prime$, $V$, $V↑\prime$, $P$, $P↑\prime$, $A$,
and $S$ represent, respectively, what that exercise calls $R + U↓n$,
$R + U↓{n-1}$, $V↓n$, $V↓{n-1}$, $p↓n\mod N$, $p↓{n-1}\mod N$, $A↓n$,
and $n\mod 2$. We will always have $$0 < V ≤ U ≤ R↑\prime ,$$
so the highest precision is needed only for $P$ and $P↑\prime$.)

\penalty-300 % better to break here than befor E3 (May 1980)
\algstep E2. [Advance $U$, $V$, $S$.] Set $T ← V$, $V ← A(U↑\prime
- U) + V↑\prime$, $V↑\prime ← T$, $A ← \lfloor U/V\rfloor$, $U↑\prime
← U$, $U ← R↑\prime - (U\mod V)$, $S ← 1 - S$.

\algstep E3. [Factor $V$.] $\biglp$Now we have $P↑2 - kNQ↑2 = (-1)↑SV$,
for some $Q$ relatively prime to $P$, by exercise 4.5.3--12(c).$\bigrp$\xskip
Set $(e↓0, e↓1, \ldotss , e↓m) ← (S,0,\ldotss,0)$,
$T ← V$. Now do the following, for $1 ≤ j ≤ m$: If $T\mod
p↓j = 0$, set $T ← T/p↓j$ and $e↓j ← e↓j + 1$, and repeat this
process until $T\mod p↓j ≠ 0$.

\algstep E4. [Solution?] If $T = 1$, output the values $(P,
e↓0, e↓1, \ldotss , e↓m)$, which comprise a solution to (18).\xskip
(If enough solutions have been generated, we may terminate the
algorithm now.)

\algstep E5. [Advance $P$, $P↑\prime$.] If $V ≠ 1$ or $U ≠ R↑\prime
$, set $T ← P$, $P ← (AP + P↑\prime)\mod N$, $P↑\prime ← T$, and return to step E2.
Otherwise the continued fraction process has started to repeat
its cycle, except perhaps for $S$, so the algorithm terminates.
$\biglp$The cycle will usually be so long that this doesn't happen,
unless $kN$ is nearly a perfect square.$\bigrp$\quad\blackslug

\yyskip  We can illustrate the application
of Algorithm↔E to relatively small numbers by considering the
case $N = 197209$, $k = 1$, $m = 3$, $p↓1 = 2$, $p↓2 = 3$, $p↓3 = 5$.
The computation proceeds as follows:
$$\vbox{\halign to size{\hfill#\tabskip0pt plus 10pt
⊗$\rt{#}$⊗$\rt{#}$⊗$\rt{#}$⊗$\rt{#}$⊗$\rt{#}$⊗$\rt{#}$⊗$\lft{#}$\tabskip0pt\cr
⊗U\hfill⊗V\hfill⊗A\hfill⊗P\hfill⊗S⊗T⊗\hfill\hbox{Output}\cr
\noalign{\vskip 3pt}
After E1:⊗888⊗1⊗0⊗444⊗0⊗\hbox{---}\cr
After E4:⊗876⊗73⊗12⊗444⊗1⊗73\cr
After E4:⊗882⊗145⊗6⊗5329⊗0⊗29\cr
After E4:⊗857⊗37⊗23⊗32418⊗1⊗37\cr
After E4:⊗751⊗720⊗1⊗159316⊗0⊗1⊗159316↑2 ≡ +2↑4 \cdot 3↑2 \cdot 5↑1\cr
After E4:⊗852⊗143⊗5⊗191734⊗1⊗143\cr
After E4:⊗681⊗215⊗3⊗131941⊗0⊗43\cr
After E4:⊗863⊗656⊗1⊗193139⊗1⊗41\cr
After E4:⊗883⊗33⊗26⊗127871⊗0⊗11\cr
After E4:⊗821⊗136⊗6⊗165232⊗1⊗17⊗\cr
After E4:⊗877⊗405⊗2⊗133218⊗0⊗1⊗133218↑2 ≡ +2↑0 \cdot 3↑4 \cdot 5↑1\cr
After E4:⊗875⊗24⊗36⊗37250⊗1⊗1⊗\937250↑2 ≡ -2↑3 \cdot 3↑1 \cdot 5↑0\cr
After E4:⊗490⊗477⊗1⊗93755⊗0⊗53\cr}}$$
Continuing the computation gives
25 outputs in the first 100 iterations; in other words, the
algorithm is finding solutions quite rapidly. But some of the solutions
are trivial. For example, if the above computation were continued
13 more times, we would obtain the output $197197↑2 ≡ 2↑4 \cdot
3↑2 \cdot 5↑0$, which is of no interest since $197197 ≡ -12$.
The first two solutions above are already enough to complete
the factorization: We have found that
$$(159316 \cdot 133218)↑2 ≡ (2↑2 \cdot 3↑3 \cdot 5↑1)↑2\;\modulo{197209};$$
thus (17) holds with $x = (159316 \cdot 133218)
\mod 197209 = 126308$, $y = 540$. By Euclid's algorithm, $\gcd(126308
- 540, 197209) = 199$; hence we obtain the pretty factorization
$$197209 = 199 \cdot 991.$$

We can get some understanding of why Algorithm E factors large numbers so successfully
by considering a heuristic analysis of its running time, following unpublished
ideas that R. \β{Schroeppel} communicated to the author in 1975. Let us assume
for convenience that $k=1$. The number of outputs needed to produce a factorization
of $N$ will be roughly proportional to the number of small primes, $m$ being
cast out. Each execution of step E3 takes about order $m\log N$ units of
time, so the total running time will be roughly proportional to $m↑2\log N\!/P$,
where $P$ is the probability of a successful output per iteration. If we make
the conservative assumption that $V$ is randomly distributed between 0 and
$2\sqrt N$, the probability $P$ is $(2\sqrt N\,)↑{-1}$ times the number of integers
$<2\sqrt N$ whose prime factors are all in the set $\{p↓1,\ldotss,p↓m\}$.
Exercise↔29 gives a lower bound for $P$, from which we conclude that the running
time is at most
$${2\sqrt N\,m↑2\log N\over m↑r/r!},\qquad\hbox{where }r=\left\lfloor\log 2\sqrt N
\over\log p↓m\right\rfloor.\eqno(21)$$
If we let $\ln m={1\over2}\sqrt{\,\ln N\ln\ln N}$, we find that
$r=\sqrt{\,\ln N\!/\!\ln\ln N}-1+O(\log\log\log N\!/\!\log\log N)$, assuming that
$p↓m=O(m\log m)$, so formula (21) reduces to
$$\textstyle\exp\biglp2\sqrt{(\ln N)(\ln\ln N)}\;+\;\dispstyle O\biglp
(\log N)↑{1/2}(\log\log N)↑{-1/2}(\log\log\log N)\bigrp\bigrp.$$
Stating this another way, the running time of Algorithm E is expected to be
at most $N↑{ε(N)}$ under reasonably plausible assumptions, where
the exponent $ε(N)\approx2\sqrt{\,\ln\ln N\!/\!\ln N}$ goes to↔0 as $N → ∞$.

When $N$ is in a practical range, we should of course be careful not to take
such asymptotic estimates too seriously. For example, if $N=10↑{50}$ we have
$N↑{1/α}=(\lg N)↑α$ when $α\approx4.75$, and the same relation holds for $α\approx
8.42$ when $N=10↑{200}$. The function $N↑{ε(N)}$ has an order of growth that
is sort of a cross between $N↑{1/α}$ and $(\lg N)↑α$; but all three of these
forms are about the same, unless $N$ is intolerably large. Extensive computational
experience by M. C. \β{Wunderlich} has shown that a well-tuned version of
Algorithm↔E performs much better than our estimate would indicate [cf.\
{\sl Lecture Notes in Math.\ \bf751} (1979), 328--342]; although $2\sqrt{
\ln\ln N\!/\!\ln N}\approx.41$ when $N=10↑{50}$,
he obtained running times of about $N↑{.15}$ while factoring thousands
of numbers in the range $10↑{13}≤N≤10↑{42}$.

Algorithm E begins its attempt to factorize $N$ by essentially replacing $N$ by
$kN$, and
this is a rather curious way to proceed (if not downright stupid). Nevertheless,
it turns out to be a good idea, since certain values of $k$ will make the $V$
numbers potentially divisible by more small primes, hence they will be more likely to
factor completely in step E3. On the other hand, a large value of $k$ will make
the $V$ numbers larger, hence they will be less likely to factor completely;
we want to balance these tendencies by choosing $k$ wisely. Consider, for example,
the divisibility of $V$ by powers of 5. We have $P↑2
- kNQ↑2 = (-1)↑SV$ in step
E3, so if 5 divides $V$ we have $P↑2 ≡ kNQ↑2 \modulo 5$. In this congruence
$Q$ cannot be a multiple of 5, since it is relatively prime
to $P$, so we may write $(P/Q)↑2 ≡ kN\modulo 5$. If we assume that $P$
and $Q$ are random relatively prime integers, so that the 24
possible pairs $(P \mod 5, Q \mod 5) ≠ (0, 0)$ are equally
likely, the probability that 5 divides $V$ is therefore ${4\over
24}$, ${8\over 24}$, 0, 0, or ${8\over 24}$ according as $kN
\mod 5$ is 0, 1, 2, 3, or 4. Similarly the probability that 25 divides
$V$ is 0, ${40\over 600}$, 0, 0, ${40\over 600}$ respectively,
unless $kN$ is a multiple of 25. In general, given an odd prime
$p$ with $(kN)↑{(p-1)/2}\mod p=1$, we find that $V$ is a multiple
of $p↑e$ with probability $2/\biglp p↑{e-1}(p + 1)\bigrp$; and the average
number of times $p$ divides $V$ comes to $2p/(p↑2 - 1)$. This
analysis, suggested by R. Schroeppel, suggests that the best
choice of $k$ is the value that maximizes
$$\chop to 12pt{\sum↓{p\,\,\hbox{\:d prime}\,}f(p, kN)\log p -
\textstyle{1\over 2}\log k,}\eqno(22)$$
where $f$ is the function defined in exercise↔28 and the sum is
over all primes $≤p↓m$,
for this is essentially the expected value of the logarithm
of $\sqrt{N}/T$ when we reach step E4.

Best results will be obtained with Algorithm↔E when both $k$ and $m$ are
well chosen. The proper choice of $m$ can only be made by experimental testing,
since the asymptotic analysis we have made is too crude to give sufficiently
precise information, and since a variety of refinements to the algorithm tend
to have unpredictable effects. For example, we can make an important improvement
by comparing step E3 with Algorithm↔A\null:
The factoring of $V$ can stop whenever we find
$T\mod p↓j ≠ 0$ and $\lfloor T/p↓j\rfloor ≤ p↓j$, since $T$
will then be either 1 or prime. If $T$ is a prime greater than $p↓m$
(it will be at most $p↓m↑2 + p↓m - 1$ in such a case), we can still output
$(P, e↓0, \ldotss , e↓m, T)$, since a complete factorization
has been obtained. The second phase of the algorithm will use
only those outputs whose prime $T$'s have occurred at least
twice. This modification gives the effect of a much longer list
of primes, without increasing the factorization time.
Wunderlich's experiments indicate that $m\approx150$ works well in the
presence of this refinement, when $N$ is in the neighborhood of $10↑{40}$.

Since step E3 is by far the most time-consuming part of the
algorithm, \α{Morrison,} \α{Brillhart,} and Schroeppel have suggested
several ways to abort this step when success becomes improbable:\xskip
(a) Whenever $T$ changes to a single-precision value, continue
only if $\lfloor T/p↓j\rfloor > p↓j$ and $3↑{T-1}\mod T ≠
1$.\xskip (b) Give up if $T$ is still $>p↓m↑2$ after casting out factors
$<{1\over 10}p↓m$.\xskip (c) Cast out factors only up to $p↓5$,
say, for batches of 100 or so consecutive $V$'s; continue the
factorization later, but only on the $V$ from each batch that
has produced the smallest residual $T$.\xskip(Before casting out the factors
up to $p↓5$, it is wise to calculate $N\mod p↓1↑{f↓1}p↓2↑{f↓2}p↓3↑{f↓3}p↓4↑{f↓4}p↓5↑{f↓5}$,
where the $f$'s are small enough to make
$p↓1↑{f↓1}p↓2↑{f↓2}p↓3↑{f↓3}p↓4↑{f↓4}p↓5↑{f↓5}$ fit in single precision, but
large enough to make $N\mod p↓i↑{f↓i+1}=0$ unlikely. One single-precision
remainder will therefore characterize the value of $N$ modulo five small primes.)

For estimates of the cycle length in the output of Algorithm↔E, see
D. R. \α{Hickerson,} {\sl Pacific J. Math.\ \bf 46} (1973),
429--432; D. \β{Shanks,} {\sl Proc.\ Boulder Number Theory Conference}
(Univ.\ of Colorado: 1972), 217--224.

\subsectionbegin{Other approaches} A completely different
method of factorization, based on composition of binary \α{quadratic
forms}, has been introduced by Daniel Shanks [{\sl Proc.\ Symp.\
Pure Math.\ \bf 20} (1971), 415--440]. Like Algorithm↔B, it
will factor a given $N$ in $O(N↑{(1/4)+ε})$ steps except under
wildly improbable circumstances.

Still another important technique has been suggested by John
M. \α{Pollard} [{\sl Proc.\ Cambridge Phil.\ Soc.\ \bf 76} (1974),
521--528]. He obtains rigorous worst-case bounds of $O(N↑{(1/4)+ε
})$ for factorization and $O(n↑{(1/8)+ε})$ for primality
testing, but with impracticably high coefficients of proportionality;
and he also gives a practical algorithm for discovering prime
factors $p$ of $N$ when $p - 1$ has no large prime factors.
The latter algorithm (see exercise↔19) is probably the first thing to try
after Algorithms A and↔B have run too long on a large $N$.

A survey paper by R. K. \α{Guy,} written in collaboration with J. H. \α{Conway},
{\sl Proc. Fifth Manitoba Conf.\ Numer.\ Math.} (1975), 49--89, gives a unique
perspective on these developments.

% new material  (C) Addison-Wesley 1980	*

\subsectionbegin{\star A theoretical upper bound} From the standpoint of
computational complexity, we would like to know if there is any method of
factorization whose running time can be proved to be $O(N↑{ε(N)})$, where
$ε(N)→0$ as $N→∞$. We showed that Algorithm↔E probably has such behavior,
but it
seems hopeless to find a rigorous proof, because continued fractions are not
sufficiently well disciplined.
The first proof that a good factorization algorithm exists in this sense was
discovered by John \α{Dixon} in 1978; Dixon showed, in fact, that it suffices
to consider a simplified version of Algorithm↔E, in which the continued
fraction apparatus is removed but the basic idea of (17) remains.\xskip
[{\sl J. Number Theory}, to appear.]

Dixon's method is simply this, assuming that $N$ is known to have at least two
distinct prime factors, and that $N$ is not divisible by the first $m$ primes
$p↓1$, $p↓2$, $\ldotss$, $p↓m$: Choose a random integer $X$ in the range
\inxf{probabilistic algorithm}
$0<X<N$, and let $V=X↑2\mod N$. If $V=0$, the number $\gcd(X,N)$ is a proper
factor of $N$. Otherwise cast out all of the small prime factors of $V$ as in
step↔E3; in other words, express $V$ in the form
$$V=p↓1↑{e↓1}\ldotss p↓m↑{e↓m}\,T,$$
where $T$ is not divisible by any of the first $m$ primes. If $T=1$, the
algorithm proceeds as in step E4 to output $(X,e↓1,\ldotss,e↓m)$, which
represents a solution to (18) with $e↓0=0$. This process continues with new
random values of $X$ until there are sufficiently many outputs to discover a
factor of $N$ by the method of exercise 12.

In order to analyze this algorithm, we want to find bounds on (a) the probability
that a random $X$ will yield an output, and (b) the probability that a large
number of outputs will be required before a factor is found. Let $P(m,N)$ be
the probability (a), i.e., the probability that $T=1$ when $X$ is chosen at
random. After $M$ values of $X$ have been tried, we will obtain $MP(m,N)$ outputs,
on the average; and the number of outputs has
a \α{binomial distribution}, so the standard deviation is less than the
square root of the mean.  The probability (b) is fairly easy to deal with, since
exercise↔13 proves that the algorithm needs more than $m+k$ outputs with
probability $≤2↑{-k}$.

Exercise 30 proves that $P(m,N)≥m↑r/(r!N)$ when $r=2\lfloor\log N\!/(2\log p↓m)
\rfloor$, so we can estimate the running time as we did in (21) but with
the quantity
$2\sqrt N$ replaced by $N$. This time we choose $\ln m=\sqrt{(\ln N\ln\ln N)/2}$,
so that
$$\eqalign{r⊗=\sqrt{2\ln N\over\ln\ln N}-1+O\left(\log\log\log N\over
\log\log N\right),\cr
\noalign{\vskip3pt}
{m↑r\over r!\,N}⊗=\exp\biglp-\sqrt{2\ln N\ln\ln N}+O(r\log\log\log N)\bigrp.\cr}$$
We will choose $M$ so that $Mm↑r\!/(r!\,N)≥4m$; thus the expected number of
outputs $MP(m,N)$ will be at least $4m$. The running time of the algorithm
is of order $Mm\log N$, plus $O(m↑3)$ steps for exercise↔12; it turns out that
$O(m↑3)$ is less than $Mm\log N$, which is
$$\textstyle\exp\biglp\sqrt{8(\ln N)(\ln\ln N)}\;+\;\dispstyle O\biglp
(\log N)↑{1/2}(\log\log N)↑{-1/2}(\log\log\log N)\bigrp\bigrp.$$
The probability that this method fails to find a factor is negligibly small,
since the probability is at most $e↑{-m/2}$ that fewer than $2m$ outputs are
obtained (see exercise↔31), while the probability is at most $2↑{-m}$ that
no factors are found from the first $2m$ outputs, and $m\grgr\ln N$. We have
proved the following slight strengthening of Dixon's original theorem:

\thbegin Theorem D. {\sl There is an algorithm whose running time is $O(N↑{ε(N)})$,
where $ε(N)=c\sqrt{\,\ln\ln N\!/\!\ln N}$ and $c$ is any constant greater than $\sqrt8$,
that finds a nontrivial factor of $N$ with probability $1-O(1/N)$, whenever
$N$ has at least two distinct prime divisorss.}\quad\blackslug

\subsectionbegin{Secret factors} Worldwide interest in the problem of
factorization increased dramatically in 1977, when
\inxf{cryptanalysis}
\inxf{secure communications}
R. L. \α{Rivest}, A. \α{Shamir}, and L. \α{Adleman} discovered a way to
encode messages that can apparently be decoded only by knowing the factors of
a large number $N$, even though the method of encoding is known to everyone.
Since a significant number of the world's greatest mathematicians have been
unable to find efficient methods of factoring, this scheme [{\sl CACM \bf21}
(1979), 120--126] almost certainly provides a secure way to protect
confidential data and communications in computer networks.

Let us imagine a small electronic device called an {\sl \β{RSA box}} that has
two large prime numbers $p$ and $q$ stored in its memory. We will assume that
$p-1$ and $q-1$ are not divisible by↔3. The RSA box is connected somehow to a
computer, and it has told the computer the product $N=pq$; however, no human
being will be able to discover the values of $p$ and $q$ except by factoring↔$N$,
since the RSA box is cleverly designed to self-destruct if anybody tries to
tamper with it. In other words,
it will erase its memory if it is jostled or if it is subjected to any
radiation that could change or read out the data stored inside.
 Furthermore, the RSA box is sufficiently reliable that it never
needs to be maintained; we simply would discard it and buy another, if an emergency
arose or if it wore out.
The prime factors $p$ and $q$ were generated by the RSA box itself, using some
scheme based on truly random phenomena in nature like cosmic rays.
\inx{Random numbers, machines for generating}
The important point is that {\sl nobody} knows $p$ or $q$, not even a person
or organization that owns or has access to this RSA box; there is no point in
bribing or blackmailing anyone or holding anybody hostage in order to discover
$N$'s factors.

To send a secret message to the owner of an RSA box whose product number is $N$,
you break the message up into a sequence of numbers $(x↓1,\ldotss,x↓k)$, where
each $x↓i$ is between 0 and↔$N$, then you transmit the numbers
$$(x↓1↑3\mod N,\;\ldotss,\;x↓k↑3\mod N).$$ The RSA box, knowing $p$ and $q$, can
decode the message, because it has precomputed a number $d<N$ such that
$3d≡1$ $\biglp\hbox{modulo }(p-1)(q-1)\bigrp$; it can now compute
$(x↑3)↑d\mod N=x$ in a reasonable amount of time, using the method of Section↔4.6.3.
Naturally the RSA box keeps this magic number $d$ to itself; in fact, the RSA box
might choose to remember only $d$ instead of $p$ and $q$, because its only duties
\inxf{cube roots}
after having computed $N$ are to protect its secrets and to take cube roots mod↔$N$.

\def\\{\spose{\raise5.0pt\hbox{\hskip2.5pt$\scriptscriptstyle3$}}\sqrt N}
If $x<\\$, the above encoding scheme is ineffective, since $x↑3\mod N=x↑3$ and
the cube root will easily be found. The \α{logarithmic law of leading digits}
in Section↔4.2.4 implies that the leading place $x↓1$ of a $k$-place message
$(x↓1,\ldotss,x↓k)$ will be less than $\\$ about $1\over3$ of the time, so
this is a problem that needs to be resolved. Exercise↔32 presents one way to do this.

The security of the RSA encoding scheme relies on the fact that nobody has been
able to discover how to take cube roots mod $N$ without knowing $N$'s factors. It
seems likely that no such method will be found, but we cannot be absolutely sure.
So far all that can be said for certain is that all of the ordinary ways to discover
cube roots will fail. For example,
there is essentially no point in trying to compute the number $d$ as a function
of $N$; the reason is that if $d$ is known, or in fact if any number $m$ of
reasonable size is known such that $x↑m\mod N=1$ holds for a significant number
of $x$'s, then we can find the factors of $N$ in a few more steps (see
exercise↔34). Thus, any method of attack based explicitly or implicitly on finding
such an $m$ can be no better than factoring.

The numbers $p$ and $q$ shouldn't merely be ``random'' primes in order to make the
RSA scheme effective. We have mentioned that $p-1$ and $q-1$ should not be
divisible by 3, since we want to ensure that unique cube roots exist modulo↔$N$.
Another condition is that $p-1$ should have at least one very large prime factor,
and so should $q-1$; otherwise $N$ can be factored using the algorithm of
exercise↔19. In fact, that algorithm essentially relies on finding a fairly
small number $m$ with the property that $x↑m\mod N$ is frequently equal to↔1,
and we have just seen that such an $m$ is dangerous. When $p-1$ and $q-1$ have
large prime factors $p↓1$ and $q↓1$, the theory in exercise↔34 implies that
$m$ is either a multiple of $p↓1q↓1$ (hence $m$ will be hard to discover) or
the probability that $x↑m≡1$ will be less than $1/p↓1q↓1$ (hence $x↑m\mod N$
will almost never be↔1).
Besides this condition, we don't want $p$ and $q$ to be
close to each other, lest Algorithm↔D succeed in discovering them; in fact,
we don't want the ratio $p/q$ to be near a simple fraction, otherwise
\α{Lehman}'s generalization of Algorithm↔C could find them.

The following procedure for generating $p$ and $q$ is almost surely unbreakable:
Start with a truly random number $p↓0$ between, say, $10↑{80}$ and $10↑{81}$.
Search for the first prime number $p↓1$ greater than $p↓0$; this will require
testing about ${1\over2}\ln p↓0\approx90$ odd numbers, and it will be sufficient
to have $p↓1$ a ``probable prime'' with probability $>1-2↑{-100}$ after 50 trials
of Algorithm↔P. Then choose another truly random number $p↓2$ between, say,
$10↑{39}$ and $10↑{40}$. Search for the first prime number $p$ of the form
$kp↓1+1$ where $k≥p↓2$, $k$ is even, and $k≡p↓1\modulo3$. This will require
testing about ${1\over6}\ln p↓1p↓2\approx45$ numbers before a prime $p$ is
found. The prime $p$ will be about 120 digits long; a similar construction can
be used to find a prime $q$ about 130 digits long.
For extra security, it is probably advisable to check that neither $p+1$ nor
$q+1$ consists entirely of rather small prime factors (see exercise↔20).
The product $N=pq$, whose order of magnitude will be about $10↑{250}$, now meets all
of our requirements, and it is inconceivable at this time that such an $N$
could be factored.

For example, suppose we knew a method that could factor a 250-digit number
$N$ in $N↑{.10}$ microseconds. This amounts to $10↑{25}$ microseconds, and there
are only 31,556,952,000,000 $\mu$s per year, so we would need more than
$3\times10↑{11}$ years of CPU time to complete the factorization. Even if a
government agency purchased 10 billion computers and set them all to working on
this problem, it would take more than 31 years before one of them would crack $N$
into factors; meanwhile the fact that the government had purchased so many
specialized machines would leak out, and people would start using 300-digit $N$'s.

Since the encoding method $x\mapsto x↑3\mod N$ is known to everyone, there are
additional advantages besides the fact that the code can be cracked only by the
RSA box. Such ``public key'' systems were first considered by W. \α{Diffie}
\inx{public key cryptography}
and M. E. \α{Hellman} in {\sl IEEE Trans. \bf IT-22} (1976), 644--651. 
As an example of what can be done when the encoding method is public knowledge,
suppose that Alice wants to communicate with Bill via electronic mail,
and suppose
each of them wants the letters to be {\sl signed} so that the receiver can be
\inxf{signatures, digital}
sure that nobody else is forging any messages. Let $E↓A(M)$ be the encoding function
for messages $M$ sent to Alice, let $D↓A(M)$ be the decoding done by Alice's
RSA box, and let $E↓B(M)$, $D↓B(M)$ be the corresponding encoding and decoding
functions for Bill's RSA box. Then Alice can send a signed message by affixing her
name and the date to some confidential message, then transmitting $E↓B\biglp
D↓A(M)\bigrp$
to Bill, using her machine to compute $D↓A(M)$. When Bill gets this message,
his RSA box converts it to $D↓A(M)$, and he knows $E↓A$ so he can compute $M=
E↓A\biglp D↓A(M)\bigrp$. This should convince him that the message did indeed
come from Alice; nobody else could have sent the message $D↓A(M)$.

We might ask, how do Alice and Bill know each other's encoding functions
$E↓A$ and $E↓B$? It wouldn't do simply to have them stored in a public file,
since some Charlie could tamper with that file, substituting an $N$ that 
he has computed by himself; Charlie could then surreptitiously intercept
and decode a private message before Alice or Bill would discover that something
is amiss. The solution is to keep the product numbers $N↓A$ and $N↓B$ in a
special public directory that has its own RSA box and its own widely publicized
product number $N↓D$. When Alice wants to know how to communicate with Bill,
she asks the directory for Bill's product number;
the directory computer sends her
a {\sl signed} message giving the value of $N↓B$. Nobody can forge such
a message, so it must be legitimate.

An interesting alternative to the RSA scheme has been proposed by Michael
\α{Rabin} [MIT Lab.\ for Comp.\ Science, report TR-212 (1979)], who suggests
encoding by the function $x↑2\mod N$ instead of $x↑3\mod N$. In this case
the decoding mechanism, which we can call a SQRT box, returns four different
\inx{square root modulo m}
messages; the reason is that four different numbers have the same square modulo↔$N$,
namely $x$,↔$-x$, $fx\mod N$, and $(-fx)\mod N$, where $f=(p↑{q-1}-q↑{p-1})\mod N$.
If we agree in advance that $x$ is even, or that $x<{1\over2}N$, then the
ambiguity drops to two messages, presumably only one of which makes any sense.
Rabin's scheme has the important property that it is provably as difficult to
find square roots mod↔$N$ as to find the factorization $N=pq$; for by taking the
square root of $x↑2\mod N$ when $x$ is chosen at random, we have probability
$1\over2$ of finding a value $y$ such that $x↑2≡y↑2$ and $x\not≡\pm y$, after
which $\gcd(x,y)=p$↔or↔$q$. However, the system has a fatal flaw that does not
seem to be present in the RSA scheme (see exercise↔33): Anyone with access to
a SQRT box can easily determine the factors of its $N$. This not only permits
cheating by dishonest employees, or threats of extortion,
it also allows people to reveal their $p$ and $q$, after which they might
claim that their ``signature'' on some transmitted
document was a forgery. Thus it is clear
that the goal of secure communication leads to subtle problems quite
different from those we usually face in the design and analysis of algorithms.
%folio 505 galley 11  (C) Addison-Wesley 1978	*
\subsectionbegin{The largest known primes} We have discussed several
computational methods elsewhere in this book that require the
use of large prime numbers, and the techniques just described
can be used to discover primes of up to, say, 25 digits
or fewer, with relative ease. Table↔1 shows the ten largest primes
that are less than the word size of typical computers.\xskip (Some
other useful primes appear in the answer to exercise↔4.6.4--57.)

\topinsert{\vbox to 520pt{\hbox{(Table 1 will go on this page, 
\inx{primes, useful}
it's being set separately)}}}

Actually much larger primes of special forms are known, and
it is occasionally important to find primes that are as large
as possible. Let us therefore conclude this section by investigating
the interesting manner in which the largest explicitly known
primes have been discovered. Such primes are of the form $2↑n
- 1$, for various special values of $n$, and so they are especially
suited to certain applications of binary computers.
%folio 508 galley 12  Bad beginning. (C) Addison-Wesley 1978	*
\def\\#1{\sqrt{\hskip1pt\lower1pt\null#1}}
A number of the form $2↑n - 1$ cannot
be prime unless $n$ is prime, since $2↑{uv} - 1$ is divisible
by $2↑u - 1$. In 1644, Marin \β{Mersenne} astonished his contemporaries
by stating, in essence, that the numbers $2↑p - 1$ are prime
for $p = 2$, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, and for
no other $p$ less than 257.\xskip (This statement appeared in connection with a
discussion of \α{perfect numbers} in the preface to his {\sl Cogitata
Physico-Mathematics}. Curiously, he also made the following remark:
``To tell if a given number of 15 or 20 digits is prime or not, all time would not
suffice for the test, whatever use is made of what is already known.'')\xskip
Mersenne, who had corresponded frequently with \α{Fermat,} \α{Descartes,} and others about
similar topics in previous years, gave no proof of his assertions, and for
over 200 years nobody knew whether he was correct or not. \α{Euler} showed that
$2↑{31}-1$ is prime in 1772, after having tried unsuccessfully to prove this
in previous years. About 100 years later, \'E. \β{Lucas} discovered that
$2↑{127}-1$ is prime, but $2↑{67}-1$ is not; therefore Mersenne was not
completely accurate. Then I. M. \α{Pervushin} proved in 1883 that $2↑{61}-1$ is
prime [cf.\ {\sl Istoriko-Mat.\ Issledovani\t\i a \bf6} (1953), 559], and this
touched off speculation that Mersenne had only made a copying
error, writing 67 for 61. Eventually other errors in Mersenne's
statement were discovered; R. E. \α{Powers} [{\sl AMM \bf 18}
(1911), 195] found that $2↑{89} - 1$ is prime, as had been conjectured
by some earlier writers, and three years later he proved that
$2↑{107} - 1$ also is prime.\xskip M. \α{Kraitchik} showed in 1922 that
$2↑{257}- 1$ is {\sl not} prime.

At any rate, numbers of the form $2↑p - 1$ are now known as {\sl Mersenne numbers},
and it is known
that the first 27 \β{Mersenne primes} are obtained for $p$ equal to
$$\baselineskip15pt
\quad\cpile{2,\,3,\,5,\,7,\,13,\,17,\,19,\,31,\,61,\,89,\,107,\,127,\,521,\,607,
\,1279,\,2203\,2281,\cr
3217,\,4253,\,4423,\,9689,\,9941,\,11213,\,19937,\,21701,\,23209,\,44497.\cr}
\eqno(23)$$
The 24th of these was found by Bryant Tuckerman
[{\sl Proc.\ Nat.\ Acad.\ Sci.\ \bf 68} (1971), 2319--2320],
and the 25th was found in 1978 by Laura Nickel and Curt Noll. Shortly
afterwards, Noll found the 26th, and David Slowinski harnessed a \α{CRAY-I}
computer to the task of discovering the 27th; see {\sl J. Recreational Math.\
\bf11} (1979), 258--261. \xskip
(Note that the prime $8191 = 2↑{13} - 1$ does not occur in
this list; Mersenne had stated that $2↑{8191} - 1$ is prime, and
others had conjectured that any Mersenne prime could perhaps
be used in the exponent.)

Since $2↑{44497} - 1$ is a 13,395-digit number, it is clear that
some special techniques have been used to prove that it is prime.
An efficient method for testing the primality of a given Mersenne number
$2↑p - 1$ was first devised by \'E. Lucas [{\sl Amer.\ J. Math.\ \bf 1}
(1878), 184--239, 289--321, especially p.\ 316] and improved
by D. H. \α{Lehmer} [{\sl Annals of Math.\ \bf 31} (1930), 419--448,
especially p.\ 443]. The Lucas--Lehmer test, which is a special
case of the method now used for testing the primality of $n$
when the factors of $n + 1$ are known, is the following:

\thbegin Theorem L. {\sl Let $q$ be an odd prime, and
define the sequence $\langle L↓n\rangle$ by the rule
$$L↓0 = 4,\qquad L↓{n+1} = (L↓n↑2 - 2)\mod (2↑q - 1).\eqno (24)$$
Then $2↑q - 1$ is prime if and only if $L↓{q-2} = 0$.}

\yyskip For example, $2↑3 - 1$ is prime since $L↓1
= (4↑2 - 2)\mod 7 = 0$. This test is particularly well suited
to binary computers, using multiple-precision arithmetic when $q$
is large, since calculation mod $(2↑q - 1)$ is so convenient;
cf.\ Section 4.3.2.

\proofbegin We will prove Theorem↔L using only
very simple principles of number theory, by investigating several
\inxf{linear recurrences}
features of recurring sequences that are of independent interest.
Consider the sequences $\langle U↓n\rangle$ and $\langle V↓n\rangle$
defined by
$$\baselineskip 15pt
\eqalign{U↓0⊗= 0,\cr V↓0⊗=2,\cr}\qquad
\eqalign{U↓1⊗= 1,\cr V↓1⊗=4,\cr}\qquad
\eqalign{U↓{n+1}⊗=4U↓n - U↓{n-1};\cr
V↓{n+1}⊗= 4V↓n - V↓{n-1}.\cr}\eqno(25)$$
The following equations are readily proved
by induction:
$$\baselineskip15pt
\eqalignno{V↓n⊗ = U↓{n+1} - U↓{n-1};⊗(26)\cr
U↓n ⊗=\biglp(2 + \\3\,)↑n - (2 - \\3\,)↑n\bigrp/\\{12};⊗(27)\cr
V↓n ⊗= (2 + \\3\,)↑n + (2 - \\3\,)↑n;⊗(28)\cr
U↓{m+n} ⊗=U↓mU↓{n+1}- U↓{m-1}U↓n.⊗(29)\cr}$$
Let us now prove an auxiliary result, when $p$ is prime and $e ≥ 1:$
$$\hbox{if}\qquad U↓n ≡ 0 \modulo {p↑e}\qquad\hbox{then}\qquad U↓{np}
≡ 0 \modulo {p↑{e+1}}.\eqno (30)$$
This follows from
the more general considerations of exercise 3.2.2--11, but a
direct proof for sequence (25) can be given. Assume that $U↓n =
bp↑e$, $U↓{n+1} = a$. By (29) and (25), $U↓{2n} = bp↑e(2a - 4bp↑e)
≡ (2a)U↓n\modulo{p↑{e+1}}$, while we have $U↓{2n+1} = U↑{2}↓{n+1}
- U↓n↑2 ≡ a↑2$. Similarly, $U↓{3n} = U↓{2n+1}U↓n - U↓{2n}U↓{n-1}≡
(3a↑2)U↓n$ and $U↓{3n+1}=U↓{2n+1}U↓{n+1}-U↓{2n}U↓n≡a↑3$. In general,
$$U↓{kn}≡(ka↑{k-1})U↓n\qquad\hbox{and}\qquad U↓{kn+1}≡a↑k\qquad\modulo{p↑{e+1}},$$
so (30) follows if we take $k = p$.

From formulas (27) and (28) we can obtain
other expressions for $U↓n$ and $V↓n$, expanding $(2 \pm \\3\,)↑n$
by the binomial theorem:
$$\chop to 12pt{U↓n = \sum ↓{k}{n\choose2k + 1}\,2↑{n-2k-1}3↑k,\qquad
V↓n = \sum ↓{k}{n\choose2k}\,2↑{n-2k+1}3↑k.}\eqno (31)$$
Now if we set $n = p$, where $p$ is an odd prime,
and if we use the fact that $p\choose k$ is a multiple of
$p$ except when $k = 0$ or $k = p$, we find that
$$U↓p ≡ 3↑{(p-1)/2},\qquad V↓p ≡ 4\qquad \modulo p.\eqno(32)$$
If $p ≠ 3$, Fermat's theorem tells us that $3↑{p-1}
≡ 1$; hence $(3↑{(p-1)/2}- 1) \* (3↑{(p-1)/2}+1)≡0$, and $3↑{(p-1)/2}≡\pm1$.
When $U↓p ≡ -1$,
we have $U↓{p+1} = 4U↓p - U↓{p-1} = 4U↓p + V↓p - U↓{p+1} ≡ -U↓{p+1}$;
hence $U↓{p+1}\mod p = 0$. When $U↓p ≡ +1$, we have $U↓{p-1}
= 4U↓p - U↓{p+1} = 4U↓p - V↓p - U↓{p-1} ≡ -U↓{p-1}$; hence $U↓{p-1}
\mod p = 0$. We have proved that, for all primes $p$,
there is an integer $ε(p)$ such that
$$U↓{p+ε(p)}\mod p=0, \qquad |ε(p)|≤1.\eqno(33)$$

Now if $N$ is any positive integer, and if $m=m(N)$ is the smallest positive
integer such that $U↓{m(N)}\mod N = 0$, we have
$$U↓n \mod N = 0\qquad\hbox{if and only if\qquad$n$ is a multiple
of $m(N)$.}\eqno (34)$$
(This number $m(N)$ is called the ``\α{rank of apparition}''
of $N$ in the sequence.) To prove (34), observe that the sequence
$U↓m$, $U↓{m+1}$, $U↓{m+2}$, $\ldots$ is congruent (modulo↔$N$) to
$aU↓0$, $aU↓1$, $aU↓2$, $\ldotss$, where $a = U↓{m+1}\mod N$ is
relatively prime to $N$ because $\gcd(U↓n, U↓{n+1}) = 1$.

With these preliminaries out of the way, we are ready to prove
Theorem↔L\null. By (24) and induction,
$$L↓n = V↓{2↑n}\mod (2↑q - 1).\eqno (35)$$
Furthermore, the identity $2U↓{n+1}
= 4U↓n + V↓n$ implies that $\gcd(U↓n, V↓n) ≤ 2$, since any common factor
of $U↓n$ and $V↓n$ must divide $U↓n$ and $2U↓{n+1}$, while $\gcd(U↓n,
U↓{n+1}) = 1$. So $U↓n$ and $V↓n$ have no odd factor in common, and
if $L↓{q-2} = 0$ we must have
$$\baselineskip15pt
\eqalign{U↓{2↑{q-1}}=U↓{2↑{q-2}}V↓{2↑{q-2}}⊗≡0\;\modulo{2↑q-1},\cr
U↓{2↑{q-2}}⊗\neqv0\modulo{2↑q-1}.\cr}$$

Now if $m=m(2↑q-1)$ is the rank of apparition of $2↑q-1$, it must be a divisor
of $2↑{q-1}$ but not of $2↑{q-2}$; thus $m=2↑{q-1}$. We will prove that $n=2↑q-1$
must therefore be prime: Let the factorization of $n$ be $p↓1↑{e↓1}\ldotss
p↓r↑{e↓r}$. All primes $p↓j$ are greater than 3, since $n$ is odd and congruent
to $(-1)↑q-1=-2\modulo 3$. From (30), (33), and (34) we know that $U↓t≡0\modulo
{2↑q-1}$, where
$$t=\lcm\biglp p↓1↑{e↓1-1}(p↓1+ε↓1),\,\ldotss,\,p↓r↑{e↓r-1}(p↓r+ε↓r)\bigrp,$$
and each $ε↓j$ is $\pm1$. It follows that $t$ is a multiple of $m=2↑{q-1}$. Let $n↓0=
\prod↓{1≤j≤r}p↓{\!j}↑{e↓j-1}(p↓j+ε↓j)$; we have $n↓0≤\prod↓{1≤j≤r}p↓{\!j}
↑{e↓j-1}(p↓j+
{1\over5}p↓j)=({6\over5})↑rn$. Also, because $p↓j+ε↓j$ is even, $t≤n↓0/2↑{r-1}$,
since a factor of two is lost each time the least common multiple of two even
numbers is taken. Combining these results, we have $m≤t≤2({3\over5})↑rn<4({3\over5}
)↑rm<3m$; hence $r≤2$ and $t=m$ or $t=2m$, a power of 2. Therefore $e↓1=1$,
$e↓r=1$, and if $n$ is not prime we must have $n=2↑q-1=(2↑k+1)(2↑l-1)$ where
$2↑k+1$ and $2↑l-1$ are prime. The latter factorization is obviously impossible when
$q$ is odd, so $n$ is prime.
%folio 512 galley 13  Total loss. (C) Addison-Wesley 1978	*
\def\bslash{\char'477 } % boldface slash (vol. 2 only)
\def\\#1{\sqrt{\hskip1pt\lower1pt\null#1}}
Conversely, suppose that $n = 2↑q
- 1$ is prime; we must show that $V↓{2↑{q-2}} ≡ 0\modulo n$.
For this purpose it suffices to prove that $V↓{2↑{q-1}} ≡ -2
\modulo n$, since $V↓{2↑{q-1}}=(V↓{2↑{q-2}})↑2 - 2$. Now
$$\eqalign{V↓{2↑{q-1}}⊗= \biglp(\\2 + \\6\,)/2\bigrp↑{n+1}
+ \biglp(\\2 - \\6\,)/2\bigrp↑{n+1}\cr
\noalign{\vskip6pt}
⊗= 2↑{-n} \sum↓{k}{n+1\choose2k}\\2↑{\,n+1-2k}\\6↑{\,2k} =
2↑{(1-n)/2}\sum ↓{k}{n+1\choose2k}\,3↑k.\cr}$$
Since $n$ is prime, the binomial coefficient$${n+1\choose2k}={n\choose2k}+
{n\choose2k-1}$$
is divisible by $n$ except when $k = 0$ and $k
= (n + 1)/2$; hence
$$2↑{(n-1)/2\,}V↓{2↑{q-1}} ≡ 1 + 3↑{(n+1)/2}\modulo n.$$
Here $2 ≡ (2↑{(q+1)/2})↑2$, so $2↑{(n-1)/2} ≡
(2↑{(q+1)/2})↑{(n-1)} ≡ 1$ by Fermat's theorem. Finally, by
a simple case of the law of \α{quadratic reciprocity} (cf.\ exercise↔23),
$3↑{(n-1)/2}≡-1$, since $n\mod 3 =
1$ and $n\mod 4= 3$. This means $V↓{2↑{q-1}} ≡ -2$, so $V↓{2↑{q-2}}≡0$.\quad
\blackslug

\yyskip
The world's largest explicitly known prime numbers have always been Mer\-senne
primes, at least from 1772 until 1980 when this book was written. But the
situation will probably change soon, since Mersenne primes are getting harder to
find, and since exercise↔27 presents an efficient test for primes of other
forms.

\exbegin{EXERCISES}

\exno 1. [10] If the sequence $d↓0$, $d↓1$, $d↓2$, $\ldots$
of trial divisors in Algorithm↔A contains a number that
is not prime, why will it never appear in the output?

\exno 2. [15] If it is known that the input $N$ to Algorithm↔A
is equal to 3 or more, could step A2 be eliminated?

\exno 3. [M20] Show that there is a number $P$ with the following
property: If $1000 ≤ n ≤ 1000000$, then $n$ is prime if and only
if $\gcd(n, P) = 1$.

\exno 4. [M29] In the notation of exercise 3.1--7 and
Section 1.2.11.3, prove that the average value of the least $n$ such that
$X↓n=X↓{\,l(n)-1}$ lies between $1.5\,Q(m)-0.5$ and $1.625\,Q(m)-0.5$.

\exno 5. [21] Use \α{Fermat}'s method (Algorithm↔D) to find the factors of 10541 by
hand, when the moduli are 3, 5, 7, and 8.

\exno 6. [M24] If $p$ is an odd prime and if $N$ is not a multiple of $p$,
prove that the number of integers $x$ such that $0≤x<p$ and $x↑2-N≡y↑2\modulo p$ has
a solution $y$ is equal to $(p\pm1)/2$.

\exno 7. [25] Discuss the problems of programming the sieve of Algorithm↔D on
a binary computer when the table entries for modulus $m↓i$ do not exactly fill
an integral number of memory words.


\trexno 8. [23] ({\sl The ``\α{sieve} of \α{Eratosthenes},''} 3rd century {\:mB.C.})\xskip 
The following procedure evidently discovers all odd prime numbers less than a given
integer $N↓{\null}$, 
since it removes all the nonprime numbers: Start with all the odd
numbers less than $N$; then successively strike out the multiples $p↓k↑2$,
$p↓k(p↓k+2)$, $p↓k(p↓k+4)$, $\ldotss$, of the $k$th prime $p↓k$, for $k=2$, 3, 4,
$\ldotss$, until reaching a prime $p↓k$ with $p↓k↑2>N$. 

Show how to adapt the
procedure just described into an algorithm that is directly suited to
efficient computer calculation, using no multiplication.

\exno 9. [M25] Let $n$ be an odd number, $n ≥ 3$. Show that if
the number $λ(n)$ of Theorem 3.2.1.2B is a divisor of $n - 1$
but not equal to $n - 1$, then $n$ must have the form $p↓1p↓2
\ldotsm p↓t$ where the $p$'s are distinct primes and $t ≥ 3$.

\trexno 10. [M26] (John \α{Selfridge}.)\xskip Prove that if, for each prime
divisor $p$ of $n - 1$, there is a number $x↓p$ such that $x↑{(n-1)/p}↓{p}
\mod n ≠ 1$ but $x↑{n-1}↓{p}\mod n = 1$, then $n$ is prime.

\exno 11. [M20] What outputs does Algorithm↔E give when $N =
197209$, $k = 5$, $m = 1$?\xskip [{\sl Hint:} $\sqrt{\hskip1pt 5 \cdot 197209} = 992
+ \bslash \overline{1, 495, 2, 495, 1, 1984}\bslash$.]

\trexno 12. [M28] Design an algorithm that uses the outputs of
Algorithm↔E to find a proper factor of $N↓{\null}$, provided that Algorithm↔E
has produced enough outputs to deduce a solution of (17).

\exno 13. [\HM25] (J. D. \α{Dixon}.)\xskip Prove that whenever the algorithm
of exercise 12 is pre\-sented with a solution $(x,e↓0,\ldotss,e↓m)$ whose exponents
are linearly dependent modulo↔2 on the exponents of previous solutions, the
probability is $2↑{1-d}$ that a factorization will be found, when $n$ has
$d$ distinct prime factors and $x$ is chosen at random.

\exno 14. [M20] Prove that the number $T$ in step E3 of Algorithm↔E
will never be a multiple of an odd prime $p$ for which $(kN)↑{(p-1)/2}
\mod p > 1$.

\trexno 15. [M34] (\α{Lucas} and \α{Lehmer}.)\xskip Let $P$ and $Q$ be relatively
prime integers, and let $U↓0 = 0$, $U↓1 = 1$, $U↓{n+1} = PU↓n -
QU↓{n-1}$ for $n ≥ 1$. Prove that if $N$ is a positive integer
relatively prime to $2P↑2 - 8Q$, and if $U↓{N+1}\mod N
= 0$, while $U↓{(N+1)/p}\mod N ≠ 0$ for each prime $p$ dividing
$N + 1$, then $N$ is prime.\xskip (This gives a test for primality
when the factors of $N + 1$ are known instead of the factors
of $N - 1$. We can evaluate $U↓m$ in $O(\log
m)$ steps; cf.\ exercise 4.6.3--26.)\xskip [{\sl Hint:} See the
proof of Theorem↔L.]

\exno 16. [M50] Are there infinitely many \α{Mersenne primes}?

\exno 17. [M25] (V. R. \α{Pratt}.)\xskip A complete proof of primality by the
converse of Fermat's theorem takes the form of a tree whose nodes have the form
$(q,x)$, where $q$ and $x$ are positive integers satisfying the following
arithmetic conditions:\xskip (i) If $(q↓1,x↓1)$, $\ldotss$, $(q↓t,x↓t)$ are the
sons of $(q,x)$ then $q=q↓1\ldotsm q↓k+1$.\xskip [In particular, if $(q,x)$
has no sons then $q=2$.]\xskip(ii) If $(r,y)$ is a son of $(q,x)$ then
$x↑{(q-1)/r}\mod q≠1$.\xskip(iii) For each node $(q,x)$, we have $x↑{q-1}\mod q=1
$.\xskip From these conditions it
follows that $q$ is prime and $x$ is a primitive root modulo $q$, for all
nodes $(q,x)$.\xskip[For example, the tree
\inx{ART ON REPRO REQUIRED}
\inx{MIX (actually 1009)}
$$\baselineskip 23pt\vbox{\halign{\hbox to size{$\hfill#\hfill$}\cr
(1009,11)\cr
(2,1)\qquad(2,1)\qquad(2,1)\qquad(2,1)\qquad(7,3)\qquad(3,2)\qquad(3,2)\qquad\qquad
\cr
\qquad\qquad\qquad\qquad\qquad\qquad(2,1)\qquad(3,2)\qquad(2,1)\qquad(2,1)\qquad\cr
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(2,1)\qquad\qquad\qquad\qquad\cr}}$$
demonstrates that 1009 is prime.]\xskip Prove that such a tree with root $(q,x)$ has
at most $f(q)$ nodes, where $f$ is a rather slowly growing function.

\trexno 18. [\HM23] Give a
heuristic proof of (7), analogous to the text's derivation of
(6). What is the approximate probability that $p↓{t-1} 
≤ \sqrt{\chop to 0pt{p↓t}}\,$?

\trexno 19. [M25] (J. M. \α{Pollard}.)\xskip Show how to compute a number
$M$ that is divisible by all primes $p$ such that $p-1$ is a divisor
of some given number
$D$.\xskip [{\sl Hint:} Consider numbers of the form $a↑n - 1$.]\xskip
Such an $M$ is useful in factorization, for by computing $\gcd(M,N)$ we
may discover a factor of $N↓{\null}$.
Extend this idea to an efficient method that has high probability
of discovering prime factors $p$ of a given large number $N↓{\null}$,
when all prime power factors of $p - 1$ are less than $10↑3$
except for at most one prime factor less than $10↑5$.\xskip [For example,
the second-largest prime dividing (14) would be detected by this method, since
it is $1 + 2↑4 \cdot 5↑2 \cdot 67 \cdot 107 \cdot 199 \cdot 41231$.]

\exno 20. [M40] Consider exercise↔19 with $p + 1$ replacing
$p - 1$.

\exno 21. [M49] Let $m(p)$ be the number of iterations required by Algorithm↔B
to cast out the prime factor $p$. Is $m(p)=O(\sqrt{\chop to 0pt p}\,)$ as $p→∞$?

\trexno 22. [M30] (M. O. \α{Rabin}.)\xskip Let $p↓n$ be the probability that Algorithm↔P
guesses wrong, given $n$. Show that $p↓n<{1\over4}$ for all $n$.

\exno 23. [M35] The {\sl \α{Jacobi symbol}\/} $({p\over q})$ is defined to be $-1$,
0, or $+1$ for all integers $p≥0$ and all odd integers $q>1$ by the rules
$({p\over q})≡p↑{(q-1)/2}\modulo q$ when $q$ is prime; $({p\over q})=
({p\over q↓1})\ldotsm({p\over q↓t})$ when $q$ is the product $q↓1\ldotsm q↓t$ of
$t$ primes (not necessarily distinct).

\def\\#1{\raise 2pt\hbox{$\scriptstyle#1$}}
\yskip\hang\textindent{a)}Prove that $({p\over q})$ satisfies the following
relationships, hence it can be computed effi\-ciently:\xskip $({\\0\over q})=0$;\xskip
$({\\1\over q})=1$;\xskip $({p\over q})=({p\mod q\over q})$;\xskip
 $({\\2\over q})=(+1,-1,-1,+1)$
according as $q\mod 8 = (1,3,5,7)$;\xskip
$({p↓1p↓2\over q})=({p↓1\over q})({p↓2\over q})$;\xskip
\lower6pt\null $({p\over q})=(-1)↑{(p-1)(q-1)/4}
({q\over p})$ if both $p$ and $q$ are odd.\xskip [The latter law, which
is a reciprocity relation reducing the evaluation of $({p\over q})$ to the
evaluation of $({q\over p})$, has been proved in exercise 1.2.4--47(d) when
both $p$ and $q$ are prime, so you may assume
its validity in that special case.]

\yskip\hang\textindent{b)}(\α{Solovay} and \α{Strassen}.)\xskip Prove that if $n$ is odd but
not prime, the number of integers $x$ such that $1≤x<n$ and $0≠({\\x\over n})≡
x↑{(n-1)/2}\modulo n$ is at most ${1\over2}\varphi(n)$.\xskip$\biglp$Thus,
the following testing procedure correctly determines whether or not a given
$n$ is prime, with probability $\lower4pt\null
≥{1\over2}$ for all fixed $n$: ``Generate $x$
at random with $1≤x<n$. If $0≠({\\x\over n})≡x↑{(n-1)/2}\modulo n$, say that
$n$ is probably prime, otherwise say that $n$ is definitely not prime.''$\bigrp$

\yskip\hang\textindent{c)}(\α{L. Monier}.)\xskip Prove that if $n$ and $x$ are
numbers for which Algorithm↔P concludes that ``$n$ is probably prime'', then
$0≠({\\x\over n})≡x↑{(n-1)/2}\modulo n$.\xskip[Hence Algorithm↔P is always
superior to the test in↔(b).]

\trexno 24. [M25] (L. \α{Adleman}.)\xskip When $n>1$ and $x>1$ are integers, $n$ odd,
let us say that $n$ ``passes the $x$
test of Algorithm↔P'' if either $x=n$ or if steps
P2--P5 lead to the conclusion that $n$ is probably prime.
Prove that, for any $N$, there exists a set of
positive integers
$x↓1$, $\ldotss$, $x↓m≤N$ with $m≤\lfloor\lg N\rfloor$ such that a positive odd
integer in the range
$1<n≤N$ is prime if and only if it passes the $x$ test of Algorithm↔P for
$x=x↓1\mod n$, $\ldotss$, $x=x↓m\mod n$. Thus, the probabilistic test for
primality can in principle be converted into a efficient test that leaves nothing
to chance.\xskip(You need not show how to compute the $x↓j$ efficiently; just
prove that they exist.)

\exno 25. [\HM41] (B. \α{Riemann}.)\xskip Prove that $$π(x)=\int↓2↑x dt/\!\ln t
+\sum\int↓{-∞}↑\sigma e↑{(t+i\tau)\ln x}dt/(t+i\tau)+O(1),$$ where the sum is
\inx{zeta function}
over all complex $\sigma+i\tau$ such that $\tau≠0$ and $\zeta(\sigma+i\tau)=0$.

\trexno 26. [M25] (R. M. \α{Robinson}.)\xskip Let $N=fr+1>1$, where $0<r≤f+1$.
Prove that $N$ is prime if, for every prime divisor $p$ of $f$, there is an
integer $x$ such that $x↑{N-1}\mod N=\gcd\biglp x↑{(N-1)/p}-1,N\bigrp=1$.

\trexno 27. [M30] Show that there is a way to test numbers of the form
$5{\cdot}2↑n+1$ for primality, using about the same amount of computer time as
the \α{Lucas}--\α{Lehmer} test for Mersenne primes in Theorem↔L.

\exno 28. [M27] Given a prime $p$ and a positive integer $d$,
what is the value of $f(p, d)$, the average number of times
$p$ divides $A↑2 - dB↑2$, when $A$ and $B$ are random integers
that are independent except for the condition $\gcd(A, B) = 1$?

\exno 29. [M25] Prove that the number of positive integers $≤n$ whose prime
factors are all contained in a given set of primes $\{p↓1,\ldotss,p↓m\}$ is at least
$m↑r/r!$, when $r=\lfloor\log n/\!\log p↓m\rfloor$ and $p↓1<\cdots<p↓m$.

\exno 30. [\HM35] (J. D. \α{Dixon} and Claus-Peter \α{Schnorr}.)\xskip
Let $p↓1<\cdots<p↓m$ be primes that do not divide the odd number $N$, and let
$r$ be an even integer $≤\log N\!/\!\log p↓m$. Prove that the number of
integers $X$ in the range $0≤X<N$ such that $X↑2\mod N=p↓1↑{e↓1}\ldotss p↓m↑{e↓m}$ is
at least $m↑r/r!$.\xskip[{\sl Hint:} Let the prime factorization of $N$ be
$q↓1↑{f↓1}\ldotss q↓d↑{f↓d}$. Show that a sequence of exponents $(e↓1,\ldotss,e↓m)$
leads to $2↑d$ solutions $X$ whenever we have $e↓1+\cdots+e↓m≤r$ and
$p↓1↑{e↓1}\ldotss p↓m↑{e↓m}$ is a quadratic residue modulo $q↓i$ for $1≤i≤d$.
Such exponent sequences can be obtained as ordered pairs $(e↓1↑\prime,\ldotss,e↓m↑\prime;
e↓1↑{\prime\prime},\ldotss,e↓m↑{\prime\prime})$ where $e↓1↑\prime+\cdots+e↓m↑\prime
≤{1\over2}r$ and $e↓1↑{\prime\prime}+\cdots+e↓m↑{\prime\prime}≤{1\over2}r$ and
$$(p↓1↑{e↓1↑\prime}\ldotss p↓m↑{e↓m↑\prime})↑{(q↓i-1)/2}≡(p↓1↑{e↓1↑{\prime\prime}}
\ldotss p↓m↑{e↓m↑{\prime\prime}})↑{(q↓i-1)/2}\modulo {q↓i}$$for $1≤i≤d$.]

\exno 31. [M20] Use formula 3.5--33 to show that the probability is less than
$e↑{-m/2}$ that \α{Dixon}'s algorithm (as described preceding Theorem↔D) obtains
fewer than $2m$ outputs.

\def\\{\spose{\raise4.5pt\hbox{\hskip2.3pt$\scriptscriptstyle3$}}\sqrt N}
\trexno 32. [M21] Show how to modify the RSA encoding scheme so that there is no
problem with messages $<\\$, and so that the length of messages is not
substantially increased.

\exno 33. [M50] Prove or disprove: If a reasonably efficient algorithm exists that
has a nonnegligible probability of being able to find $x\mod N$,
given a number $N=pq$ whose prime factors satisfy $p≡q≡2\modulo3$
and given the value of $x↑3\mod N$,
then there is a reasonably efficient
algorithm that has a nonnegligible probability of being able to find the factors
of↔$N$.\xskip[If this could be proved, it would not only show that the cube
root problem is as difficult as factoring, it would also show that the RSA scheme
has the same fatal flaw as the SQRT scheme.]

\exno 34. [M30] (Peter \α{Weinberger}.)\xskip Suppose $N=pq$ in the RSA scheme,
and suppose you know a number $m$ such that $x↑m\mod N=1$ for at least
$10↑{-12}$ of all positive integers $x$. Explain how you would go about factoring
$N$ without great difficulty, if $m$ is not too large.

\trexno 35. [M35] (A. \α{Shamir}.)\xskip Consider an abstract computer that can perform
\inx{automata}
the operations $x+y$, $x-y$, $x\cdot y$, and $\lfloor x/y\rfloor$ on integers
$x$ and $y$ of arbitrary length, in just one unit of time, no matter how large
those integers are. The machine stores integers in a random-access memory and it
can select different program steps depending on whether or not $x=y$, given
$x$ and $y$. The purpose of this exercise is to demonstrate that there is
an amazingly fast way to factorize numbers on such a computer.\xskip
$\biglp$Therefore it will
probably be quite difficult to show that factorization is inherently complicated
on {\sl real\/} machines, although we suspect that it is.$\bigrp$

\yskip\hang\textindent{a)}Find a way to compute $n!$ in $O(\log n)$ steps on
such a computer, given an integer value $n≥2$.\xskip[{\sl Hint:} If $
A$ is a sufficiently large integer, the binomial coefficients ${m\choose k}=
m!/(m-k)!\,k!$ can be computed readily from the value of $(A+1)↑m$.]

\yskip\hang\textindent{b)}Show how to compute a number $f(n)$ in $O(\log n)$ steps
on such a computer, given an integer value $n≥2$, having the following
properties:\xskip$f(n)=n$ if $n$ is
prime, otherwise $f(n)$ is a proper (but not necessarily prime) divisor of
$n$.\xskip[{\sl Hint:} If $n≠4$, one such function $f(n)$ is $\gcd\biglp m(n),
n\bigrp$, where $m(n)=\min\leftset m\relv m!\mod n=0\rightset$.]

\yskip\noindent$\biglp$As a consequence of (b), we can completely factor a given
number $n$ by doing only $O(\log n)↑2$ arithmetic operations on arbitrarily
large integers: Given a partial factorization $n=n↓1\ldotsm n↓r$, each
nonprime $n↓i$ can be replaced by $f(n↓i)\cdot\biglp n↓i/f(n↓i)\bigrp$ in
a total of $\sum O(\log n↓i)=O(\log n)$ steps, and this refinement operation can be
repeated until all $n↓i$ are prime.$\bigrp$
\vfill\eject\end